Submission #119047

#TimeUsernameProblemLanguageResultExecution timeMemory
119047nvmdavaSails (IOI07_sails)C++17
100 / 100
325 ms3824 KiB
#include <bits/stdc++.h> using namespace std; int tree[100005], lazy[400005]; vector<pair<int, int> > v; void update(int id, int l, int r, int L, int R){ if(l == L && r == R){ lazy[id]++; return; } int m = (l + r) >> 1; if(m < L) update(id << 1 | 1, m + 1, r, L, R); else if(m >= R) update(id << 1, l, m, L, R); else { update(id << 1, l, m, L, m); update(id << 1 | 1, m + 1, r, m + 1, R); } } void push(int id, int l, int r){ if(l == r) tree[l] += lazy[id]; else { lazy[id << 1] += lazy[id]; lazy[id << 1 | 1] += lazy[id]; } lazy[id] = 0; } int query(int id, int l, int r, int x){ push(id, l, r); if(l == r) return tree[l]; int m = (l + r) >> 1; if(m < x) return query(id << 1 | 1, m + 1, r, x); return query(id << 1, l, m, x); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin>>n; for(int i = 1; i <= n; i++){ int h, k; cin>>h>>k; v.push_back({h, k}); } sort(v.begin(), v.end()); for(auto& x : v){ int h = x.first; int k = x.second; int idr = h - k + 1; int idl = idr; int val = query(1, 1, 100000, idr); for(int j = 19; j >= 0; j--){ if(idl - (1 << j) > 0 && query(1, 1, 100000, idl - (1 << j)) == val) idl -= (1 << j); if(idr + (1 << j) <= h && query(1, 1, 100000, idr + (1 << j)) == val) idr += (1 << j); } int ri = h - idr; int le = k - ri; if(le) update(1, 1, 100000, idl, idl + le - 1); if(ri) update(1, 1, 100000, idr + 1, idr + ri); } long long res = 0; for(int i = 1; i <= 100000; i++){ long long a = query(1, 1, 100000, i); res += a * (a - 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...