Submission #670364

#TimeUsernameProblemLanguageResultExecution timeMemory
670364Koful123Sails (IOI07_sails)C++17
100 / 100
80 ms3184 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define endl "\n" #define pb push_back #define ff first #define ss second #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() const int N = (int) 2e5 + 5,lg = 20; struct Fenwick{ int n; vector<int> fw; Fenwick(int _n){ fw.assign((n = _n) + 1,0); }; void upd(int pos,int x){ for(; pos <= n; pos += (pos & -pos)){ fw[pos] += x; } } void upd(int l,int r,int x){ if(l > r) return; upd(l,1), upd(r + 1,-1); // cout << l << ' ' << r << endl; } int get(int pos){ int res = 0; for(; pos; pos -= (pos & -pos)){ res += fw[pos]; } return res; } void find(int sz,int k,int end){ int val = get(sz),l = 1,r = sz; while(l < r){ int m = (l + r) / 2; if(get(m) == val) r = m; else l = m + 1; } int pre = l; l = sz,r = end; while(l < r){ int m = (l + r + 1) / 2; if(get(m) == val) l = m; else r = m - 1; } upd(pre,pre + (l - sz),1); upd(l + 1,l + k - (l - sz + 1),1); } }; void solve(){ int n; cin >> n; vector<pair<int,int>> v(n); for(auto &[x,y] : v){ cin >> x >> y; } sort(all(v)); Fenwick fw(v[n-1].ff); for(int i = 0; i < n; i++){ fw.find(v[i].ff - v[i].ss + 1,v[i].ss,v[i].ff); } int res = 0; for(int i = 1; i <= v[n-1].ff; i++){ res += fw.get(i) * (fw.get(i) - 1) / 2; } cout << res << endl; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; while(t--) solve(); 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...