Submission #756091

#TimeUsernameProblemLanguageResultExecution timeMemory
756091SanguineChameleonSails (IOI07_sails)C++17
70 / 100
1072 ms1492 KiB
#include <bits/stdc++.h> using namespace std; void just_do_it(); int main() { #ifdef KAMIRULEZ freopen("kamirulez.inp", "r", stdin); freopen("kamirulez.out", "w", stdout); #endif ios_base::sync_with_stdio(0); cin.tie(0); just_do_it(); return 0; } const int maxn = 1e5 + 20; pair<int, int> a[maxn]; int cnt[maxn]; int h; int get(int pos) { return cnt[pos]; } void update(int lt, int rt) { for (int i = lt; i <= rt; i++) { cnt[i]++; } } int find_max(int lt, int rt, int val) { int res = -1; for (int i = lt; i <= rt; i++) { if (get(i) >= val) { res = i; } else { break; } } return res; } int find_min(int lt, int rt, int val) { int res = -1; for (int i = rt; i >= lt; i--) { if (get(i) <= val) { res = i; } else { break; } } return res; } void just_do_it() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i].first >> a[i].second; } sort(a + 1, a + n + 1); h = a[n].first; for (int i = 1; i <= n; i++) { int rt2 = a[i].first; int rem = a[i].second; int mt = rt2 - rem + 1; int val = get(mt); int rt1 = find_max(mt, h, val); int lt = find_min(1, mt, val); if (rt1 < rt2) { update(rt1 + 1, rt2); rem -= rt2 - rt1; } if (rem > 0) { update(lt, lt + rem - 1); } } long long res = 0; for (int i = 1; i <= h; i++) { res += 1LL * cnt[i] * (cnt[i] - 1) / 2; } cout << res; }
#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...