Submission #1226806

#TimeUsernameProblemLanguageResultExecution timeMemory
1226806VMaksimoski008Sails (IOI07_sails)C++20
100 / 100
97 ms1984 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 1e5 + 5; struct fenwick { int n; vector<ll> tree; fenwick(int _n) : n(_n+10), tree(n+20) {} void update(int p, ll v) { for(p++; p<n; p+=p&-p) tree[p] += v; } ll query(int p) { ll ans = 0; for(p++; p; p-=p&-p) ans += tree[p]; return ans; } void update(int l, int r, ll v) { update(l, v); update(r+1, -v); } } fwt(N); signed main() { int n; cin >> n; vector<array<int, 2> > a(n+1); for(int i=1; i<=n; i++) cin >> a[i][0] >> a[i][1]; sort(a.begin()+1, a.end()); ll ans = 0; fwt.update(0, 0, (ll)1e10); for(int i=1; i<=n; i++) { int R = a[i][0], L = a[i][0]-a[i][1]+1; if(fwt.query(L) < fwt.query(L-1)) { fwt.update(L, R, 1); continue; } int l=L, r=R, c=1; while(l <= r) { int mid = (l + r) / 2; if(fwt.query(L) == fwt.query(mid)) c = mid-L+1, l = mid + 1; else r = mid - 1; } l=1, r=L; int p = L; while(l <= r) { int mid = (l + r) / 2; if(fwt.query(mid) == fwt.query(L)) p = mid, r = mid - 1; else l = mid + 1; } fwt.update(p, p+c-1, 1); if(L+c <= R) fwt.update(L+c, R, 1); } for(int i=1; i<N; i++) { ll x = fwt.query(i); ans += x * (x - 1) / 2; } cout << ans << '\n'; }
#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...