/*PA2015 etap1 Siano*/ #include<iostream> #include<vector> #include<algorithm> using namespace std; int przedzialIlosc; int przedzialOd[600000]; long long przedzialChwila[600000]; long long przedzialPodstawa[600000]; long long szukany; vector<int>::iterator znaleziony; long long chwila, wys; long long skoszenie; long long wynik = 0LL; int main() { ios_base::sync_with_stdio(0); int n, m; cin >> n >> m; vector<int> trawy(n); vector<long long> sumy(n + 1, 0); for(auto &tr : trawy) cin >> tr; sort(trawy.begin(), trawy.end()); for(int i = trawy.size() - 1; i >= 0; --i) sumy[i] = sumy[i + 1] + trawy[i]; przedzialIlosc = 1; przedzialOd[1] = 0; przedzialChwila[1] = 0; przedzialPodstawa[1] = 0; przedzialOd[2] = n; for(int i = 0; i < m; ++i) { wynik = 0; cin >> chwila >> wys; for(int j = przedzialIlosc; j > 0; --j) { szukany = (wys - przedzialPodstawa[j]) / (chwila - przedzialChwila[j]); if((wys - przedzialPodstawa[j]) % (chwila - przedzialChwila[j])) ++szukany; znaleziony = lower_bound(trawy.begin() + przedzialOd[j], trawy.begin() + przedzialOd[j + 1], szukany); if(znaleziony == trawy.begin() + przedzialOd[j + 1]) break; if(znaleziony == trawy.begin() + przedzialOd[j]) { skoszenie = przedzialPodstawa[j] * (przedzialOd[j + 1] - przedzialOd[j]) + (sumy[przedzialOd[j]] - sumy[przedzialOd[j + 1]]) * (chwila - przedzialChwila[j]) - wys * (przedzialOd[j + 1] - przedzialOd[j]); wynik += skoszenie; przedzialIlosc = j; przedzialChwila[j] = chwila; przedzialPodstawa[j] = wys; przedzialOd[j + 1] = n; } else { skoszenie = przedzialPodstawa[j] * (przedzialOd[j + 1] - (znaleziony - trawy.begin())) + (sumy[znaleziony - trawy.begin()] - sumy[przedzialOd[j + 1]]) * (chwila - przedzialChwila[j]) - wys * (przedzialOd[j + 1] - (znaleziony - trawy.begin())); wynik += skoszenie; przedzialIlosc = j + 1; przedzialOd[j + 1] = znaleziony - trawy.begin(); przedzialChwila[j + 1] = chwila; przedzialPodstawa[j + 1] = wys; przedzialOd[j + 2] = n; break; } } cout << wynik << endl; } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | /*PA2015 etap1 Siano*/ #include<iostream> #include<vector> #include<algorithm> using namespace std; int przedzialIlosc; int przedzialOd[600000]; long long przedzialChwila[600000]; long long przedzialPodstawa[600000]; long long szukany; vector<int>::iterator znaleziony; long long chwila, wys; long long skoszenie; long long wynik = 0LL; int main() { ios_base::sync_with_stdio(0); int n, m; cin >> n >> m; vector<int> trawy(n); vector<long long> sumy(n + 1, 0); for(auto &tr : trawy) cin >> tr; sort(trawy.begin(), trawy.end()); for(int i = trawy.size() - 1; i >= 0; --i) sumy[i] = sumy[i + 1] + trawy[i]; przedzialIlosc = 1; przedzialOd[1] = 0; przedzialChwila[1] = 0; przedzialPodstawa[1] = 0; przedzialOd[2] = n; for(int i = 0; i < m; ++i) { wynik = 0; cin >> chwila >> wys; for(int j = przedzialIlosc; j > 0; --j) { szukany = (wys - przedzialPodstawa[j]) / (chwila - przedzialChwila[j]); if((wys - przedzialPodstawa[j]) % (chwila - przedzialChwila[j])) ++szukany; znaleziony = lower_bound(trawy.begin() + przedzialOd[j], trawy.begin() + przedzialOd[j + 1], szukany); if(znaleziony == trawy.begin() + przedzialOd[j + 1]) break; if(znaleziony == trawy.begin() + przedzialOd[j]) { skoszenie = przedzialPodstawa[j] * (przedzialOd[j + 1] - przedzialOd[j]) + (sumy[przedzialOd[j]] - sumy[przedzialOd[j + 1]]) * (chwila - przedzialChwila[j]) - wys * (przedzialOd[j + 1] - przedzialOd[j]); wynik += skoszenie; przedzialIlosc = j; przedzialChwila[j] = chwila; przedzialPodstawa[j] = wys; przedzialOd[j + 1] = n; } else { skoszenie = przedzialPodstawa[j] * (przedzialOd[j + 1] - (znaleziony - trawy.begin())) + (sumy[znaleziony - trawy.begin()] - sumy[przedzialOd[j + 1]]) * (chwila - przedzialChwila[j]) - wys * (przedzialOd[j + 1] - (znaleziony - trawy.begin())); wynik += skoszenie; przedzialIlosc = j + 1; przedzialOd[j + 1] = znaleziony - trawy.begin(); przedzialChwila[j + 1] = chwila; przedzialPodstawa[j + 1] = wys; przedzialOd[j + 2] = n; break; } } cout << wynik << endl; } return 0; } |