Submission #114291

#TimeUsernameProblemLanguageResultExecution timeMemory
114291popovicirobertSails (IOI07_sails)C++14
100 / 100
86 ms2816 KiB
#include <bits/stdc++.h> #define lsb(x) (x & (-x)) #define ll long long #define ull unsigned long long // 217 // 44 using namespace std; const int MAXH = (int) 1e5; struct Fenwick { vector <int> aib; int n; inline void init(int _n) { n = _n; aib.resize(n + 1, 0); } inline void update(int pos, int val) { for(int i = pos; i <= n; i += lsb(i)) { aib[i] += val; } } inline int query(int pos) { int ans = 0; for(int i = pos; i > 0; i -= lsb(i)) { ans += aib[i]; } return ans; } }; int main() { //ifstream cin("A.in"); //ofstream cout("A.out"); int i, n; ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> n; vector <int> h(n + 1), k(n + 1), ord(n + 1); for(i = 1; i <= n; i++) { cin >> h[i] >> k[i]; ord[i] = i; } sort(next(ord.begin()), ord.end(), [&](const int &a, const int &b) { return h[a] < h[b]; }); Fenwick fen; fen.init(MAXH); for(i = 1; i <= n; i++) { int val = fen.query(h[ord[i]] - k[ord[i]] + 1); int l = 0, r = 0; for(int step = 1 << 16; step; step >>= 1) { if(l + step <= h[ord[i]] && fen.query(l + step) > val) { l += step; } if(r + step <= h[ord[i]] && fen.query(r + step) >= val) { r += step; } } l++; fen.update(r + 1, 1), fen.update(h[ord[i]] + 1, -1); fen.update(l, 1), fen.update(l + k[ord[i]] - (h[ord[i]] - r), -1); } ll ans = 0; for(i = 1; i <= MAXH; i++) { int cur = fen.query(i); ans += 1LL * cur * (cur - 1) / 2; } cout << ans; //cin.close(); //cout.close(); 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...