#include <bits/stdc++.h> using namespace std; typedef long long LL; template<typename TH> void debug_vars(const char* data, TH head){ cerr << data << "=" << head << "\n"; } template<typename TH, typename... TA> void debug_vars(const char* data, TH head, TA... tail){ while(*data != ',') cerr << *data++; cerr << "=" << head << ","; debug_vars(data+1, tail...); } #ifdef LOCAL #define debug(...) debug_vars(#__VA_ARGS__, __VA_ARGS__) #else #define debug(...) (__VA_ARGS__) #endif ///////////////////////////////////////////////////////// const int MaxLen = 500005, MaxQ = 500005; int length, numQueries; LL speeds[MaxLen]; LL speedsPref[MaxLen]; // sumy prefiksowe po klosach void input(){ scanf("%d%d", &length, &numQueries); for(int i = 1; i <= length; i++){ scanf("%lld", &speeds[i]); } sort(speeds+1, speeds+length+1); } void precomp(){ speedsPref[0] = 0; for(int i = 1; i <= length; i++){ speedsPref[i] = speedsPref[i-1] + speeds[i]; } } int main(){ input(); precomp(); // pary sa postaci (x,t,h): ostatnie ciecie w czasie t dotyczylo // klosow o pozycjach co najmniej x i scielo je do wysokosci h vector<tuple<LL,LL,LL>> lastCut; lastCut.emplace_back(0,0,0); for(int query = 0; query < numQueries; query++){ LL cTime, cHeight; scanf("%lld%lld", &cTime, &cHeight); // znajdujemy: pozycje pierwszego scietego klosa oraz laczna // wysokosc klosow LL lastFound = length+1; // pierwszy od lewej sciety klos w operacji LL sumCuts = 0; // laczna wysokosc while(lastCut.size() > 0){ LL cutPos, cutTime, cutHeight; tie(cutPos, cutTime, cutHeight) = *lastCut.rbegin(); LL diffTime = cTime - cutTime; LL diffHeight = cHeight - cutHeight; // jak szybko klos musi rosnac, bysmy mogli go sciac? LL needSpeed; if(diffHeight <= 0){ // scinamy nie wyzej, wiec i tak zetniemy wszystko needSpeed = 0; } else { // scinamy wyzej, musi byc ceil(dh / dt) needSpeed = (diffHeight+diffTime-1) / diffTime; } //debug(needSpeed); // znajdujemy pierwszy klos do sciecia LL firstCut = distance(speeds, lower_bound(speeds+1, speeds+length+1, needSpeed)); firstCut = max(firstCut, cutPos); // na te chwile tniemy tylko dotad // czy juz to scielismy? wtedy skonczylismy z cieciem if(firstCut >= lastFound) break; // dodajemy do wyniku laczna wysokosc; jest to: // (suma predkosci na [firstCut,lastFound-1])*dt // - (dlugosc przedzialu) * diffHeight LL speedAddend = (speedsPref[lastFound-1] - speedsPref[firstCut-1]) * diffTime, heightAddend = (lastFound-firstCut) * diffHeight; sumCuts += (speedAddend - heightAddend); lastFound = firstCut; // nie zostalo nic niescietego? zrzucamy ze "stosu" if(firstCut <= cutPos){ lastCut.pop_back(); } else { // koniec przechodzenia break; } } // wrzucamy nasz przedzial if(lastFound <= length){ lastCut.emplace_back(lastFound, cTime, cHeight); } printf("%lld\n", sumCuts); /*debug(query); for(auto& C : lastCut){ LL x, t, h; tie(x,t,h) = C; debug(x, t, h); }*/ //lastTime = cTime; } }
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 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 | #include <bits/stdc++.h> using namespace std; typedef long long LL; template<typename TH> void debug_vars(const char* data, TH head){ cerr << data << "=" << head << "\n"; } template<typename TH, typename... TA> void debug_vars(const char* data, TH head, TA... tail){ while(*data != ',') cerr << *data++; cerr << "=" << head << ","; debug_vars(data+1, tail...); } #ifdef LOCAL #define debug(...) debug_vars(#__VA_ARGS__, __VA_ARGS__) #else #define debug(...) (__VA_ARGS__) #endif ///////////////////////////////////////////////////////// const int MaxLen = 500005, MaxQ = 500005; int length, numQueries; LL speeds[MaxLen]; LL speedsPref[MaxLen]; // sumy prefiksowe po klosach void input(){ scanf("%d%d", &length, &numQueries); for(int i = 1; i <= length; i++){ scanf("%lld", &speeds[i]); } sort(speeds+1, speeds+length+1); } void precomp(){ speedsPref[0] = 0; for(int i = 1; i <= length; i++){ speedsPref[i] = speedsPref[i-1] + speeds[i]; } } int main(){ input(); precomp(); // pary sa postaci (x,t,h): ostatnie ciecie w czasie t dotyczylo // klosow o pozycjach co najmniej x i scielo je do wysokosci h vector<tuple<LL,LL,LL>> lastCut; lastCut.emplace_back(0,0,0); for(int query = 0; query < numQueries; query++){ LL cTime, cHeight; scanf("%lld%lld", &cTime, &cHeight); // znajdujemy: pozycje pierwszego scietego klosa oraz laczna // wysokosc klosow LL lastFound = length+1; // pierwszy od lewej sciety klos w operacji LL sumCuts = 0; // laczna wysokosc while(lastCut.size() > 0){ LL cutPos, cutTime, cutHeight; tie(cutPos, cutTime, cutHeight) = *lastCut.rbegin(); LL diffTime = cTime - cutTime; LL diffHeight = cHeight - cutHeight; // jak szybko klos musi rosnac, bysmy mogli go sciac? LL needSpeed; if(diffHeight <= 0){ // scinamy nie wyzej, wiec i tak zetniemy wszystko needSpeed = 0; } else { // scinamy wyzej, musi byc ceil(dh / dt) needSpeed = (diffHeight+diffTime-1) / diffTime; } //debug(needSpeed); // znajdujemy pierwszy klos do sciecia LL firstCut = distance(speeds, lower_bound(speeds+1, speeds+length+1, needSpeed)); firstCut = max(firstCut, cutPos); // na te chwile tniemy tylko dotad // czy juz to scielismy? wtedy skonczylismy z cieciem if(firstCut >= lastFound) break; // dodajemy do wyniku laczna wysokosc; jest to: // (suma predkosci na [firstCut,lastFound-1])*dt // - (dlugosc przedzialu) * diffHeight LL speedAddend = (speedsPref[lastFound-1] - speedsPref[firstCut-1]) * diffTime, heightAddend = (lastFound-firstCut) * diffHeight; sumCuts += (speedAddend - heightAddend); lastFound = firstCut; // nie zostalo nic niescietego? zrzucamy ze "stosu" if(firstCut <= cutPos){ lastCut.pop_back(); } else { // koniec przechodzenia break; } } // wrzucamy nasz przedzial if(lastFound <= length){ lastCut.emplace_back(lastFound, cTime, cHeight); } printf("%lld\n", sumCuts); /*debug(query); for(auto& C : lastCut){ LL x, t, h; tie(x,t,h) = C; debug(x, t, h); }*/ //lastTime = cTime; } } |