Submission #121871

#TimeUsernameProblemLanguageResultExecution timeMemory
121871turbatSails (IOI07_sails)C++14
100 / 100
325 ms3200 KiB
#include <bits/stdc++.h> using namespace std; #define N 100005 int n, mh; long long sum, cnt[N], s[N], ans, p, uld, avr; pair <int, int> mast[N]; inline void solve (int l){ if (l > mh) return; p = l; long long th = mh; while (!cnt[p]) p++; for (int i = p + 1;i <= th;i++){ if((s[i] - s[l - 1]) * (p - l + 1) >= (s[p] - s[l - 1]) * (i - l + 1)){ p = i; } long long nw = l - 1 + ((s[th] - s[l - 1]) * (i - l + 1)) / (s[i] - s[l - 1]); th = min(th, nw); if ((s[th] - s[l - 1]) * (p - l + 1) <= (s[p] - s[l - 1]) * (i - l + 2)) break; } sum = s[p] - s[l - 1]; avr = sum / (p - l + 1); uld = sum % (p - l + 1); ans += uld * avr; ans += (p - l + 1) * avr * (avr - 1) / 2; solve (p + 1); } int main (){ ios_base::sync_with_stdio(NULL); cin.tie(NULL); cin >> n; for (int i = 0;i < n;i++){ cin >> mast[i].first>> mast[i].second; mh = max(mh, mast[i].first); cnt[mast[i].first + 1]--; cnt[mast[i].first - mast[i].second + 1]++; } for (int i = 1;i <= mh;i++) { cnt[i] += cnt[i - 1]; s[i] = s[i - 1] + cnt[i]; } solve (1); cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...