Submission #72696

#TimeUsernameProblemLanguageResultExecution timeMemory
72696Hoget157Sails (IOI07_sails)C++14
100 / 100
170 ms9812 KiB
#include <bits/stdc++.h> #define INF 1e+18 #define int long long #define LIM 100010 using namespace std; typedef pair<int,int> P; int bit[LIM]; void add(int i,int x){ while(i < LIM){ bit[i] += x; i += i & -i; } } int get(int i){ int s = 0; while(i){ s += bit[i]; i -= i & -i; } return s; } int lb(int x){ int low = 0,up = LIM; while(up - low > 1){ int mid = (low + up) / 2; if(get(mid) <= x) up = mid; else low = mid; } return up; } signed main(){ int n,ans = 0; vector<P> vec; cin >> n; for(int i = 0;i < n;i++){ int a,b; cin >> a >> b; vec.push_back(P(a,b)); } sort(vec.begin(),vec.end()); for(P p : vec){ int h = p.first,k = p.second,num = get(h - k + 1),i1 = lb(num),i2 = lb(num - 1); if(i2 < h + 1){ add(i2,1); add(h + 1,-1); add(i1,1); add(i1 + k - (h + 1 - i2),-1); }else{ add(i1,1); add(i1 + k,-1); } } for(int i = 0;i < LIM;i++){ int s = get(i); ans += s * (s - 1) / 2; } cout << ans << endl; 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...