Submission #1235335

#TimeUsernameProblemLanguageResultExecution timeMemory
1235335ssitaramSails (IOI07_sails)C++20
100 / 100
59 ms1604 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; struct BIT { int n; vector<int> T; BIT(int sz) : n(sz), T(n + 1) {} void inc(int i, int v) { ++i; for (; i <= n; i += i & -i) { T[i] += v; } } void incr(int l, int r) { if (l > r) return; inc(l, 1); inc(r + 1, -1); } int val(int i) { ++i; int res = 0; for (; i > 0; i -= i & -i) { res += T[i]; } return res; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<pair<int, int>> masts(n); for (pair<int, int>& i : masts) cin >> i.first >> i.second; sort(masts.begin(), masts.end()); BIT bit(masts.back().first); auto last = [&bit](int k) -> int { int lo = -1, hi = bit.n - 1; while (lo < hi) { int h = (lo + hi + 1) / 2; if (bit.val(h) > k) { hi = h - 1; } else { lo = h; } } return lo; }; for (pair<int, int>& i : masts) { int st = bit.n - i.first; int en = st + i.second - 1; int a = max(last(bit.val(en) - 1) + 1, st); int b = last(bit.val(en)); bit.incr(st, a - 1); int cnt = en - a + 1; bit.incr(b - cnt + 1, b); } ll ans = 0; for (int i = 0; i < bit.n; ++i) { ll cnt = bit.val(i); ans += cnt * (cnt - 1) / 2; } cout << ans << '\n'; return 0; }
#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...