Submission #500677

#TimeUsernameProblemLanguageResultExecution timeMemory
500677600MihneaSails (IOI07_sails)C++17
100 / 100
376 ms5224 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int gauss(int x) { return x * (x + 1) / 2; } struct Data { int total; int need; }; bool operator < (Data a, Data b) { return a.total < b.total; } const int N = (int) 1e5 + 7; const int INF = (int) 1e18; int n; Data guys[N]; int lazy[4 * N]; int innerValue[N]; int limit; void push(int v, int tl, int tr) { if (lazy[v]) { if (tl == tr) { innerValue[tl] += lazy[v]; } else { lazy[2 * v] += lazy[v]; lazy[2 * v + 1] += lazy[v]; } lazy[v] = 0; } } void add(int v, int tl, int tr, int l, int r) { push(v, tl, tr); if (tr < l || r < tl) { return; } if (l <= tl && tr <= r) { lazy[v]++; push(v, tl, tr); return; } int tm = (tl + tr) / 2; add(2 * v, tl, tm, l, r); add(2 * v + 1, tm + 1, tr, l, r); } int getValue(int v, int tl, int tr, int i) { push(v, tl, tr); if (tr < i || i < tl) { assert(0); } if (tl == tr) { return innerValue[tl]; } int tm = (tl + tr) / 2; if (i <= tm) { return getValue(2 * v, tl, tm, i); } else { return getValue(2 * v + 1, tm + 1, tr, i); } } void add(int l, int r) { if (l > r) { return; } add(1, 1, limit, l, r); } int get(int i) { return getValue(1, 1, limit, i); } signed main() { ios::sync_with_stdio(0); cin.tie(0); //freopen ("input", "r", stdin); cin >> n; for (int i = 1; i <= n; i++) { cin >> guys[i].total >> guys[i].need; } sort(guys + 1, guys + n + 1); limit = guys[n].total; for (int i = 1; i <= n; i++) { int total = guys[i].total; int need = guys[i].need; /// cnt e in ordine ordine descrescatoare int L = total - need + 1; int R = total; int cntL = get(L); int Lfirst = L, Llast = L; /// binary search to find them { int low = 1, high = L; while (low <= high) { int mid = (low + high) / 2; if (get(mid) == cntL) { Lfirst = mid; high = mid - 1; } else { low = mid + 1; } } } { int low = L, high = total; while (low <= high) { int mid = (low + high) / 2; if (get(mid) == cntL) { Llast = mid; low = mid + 1; } else { high = mid - 1; } } } int cntOfL = Llast - L + 1; int firstActual = Lfirst; int lastActual = Lfirst + cntOfL - 1; add(firstActual, lastActual); add(Llast + 1, R); } int total = 0; for (int i = 1; i <= limit; i++) { total += gauss(get(i) - 1); } cout << total << "\n"; 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...