Submission #828710

#TimeUsernameProblemLanguageResultExecution timeMemory
828710minhcoolComparing Plants (IOI20_plants)C++17
27 / 100
297 ms15692 KiB
//#define local #ifndef local #include "plants.h" #endif #include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; //#define int long long #define fi first #define se second #define pb push_back #define mp make_pair typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef pair<ii, ii> iiii; const int N = 3e5 + 5; const int oo = 1e9 + 7, mod = 1e9 + 7; mt19937 rng(1); int rnd(int l, int r){ int temp = rng() % (r - l + 1); return abs(temp) + l; } int a[N]; ii mini[N << 2]; int laz[N << 2]; void build(int id, int l, int r){ if(l == r){ mini[id] = {a[l], l}; return; } int mid = (l + r) >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); mini[id] = min(mini[id << 1], mini[id << 1 | 1]); } void lazy(int id){ int t = laz[id]; if(!t) return; mini[id << 1].fi += t; mini[id << 1 | 1].fi += t; laz[id << 1] += t; laz[id << 1 | 1] += t; laz[id] = 0; } void upd(int id, int l, int r, int L, int R, int val){ if(l > R || r < L || l > r) return; if(l >= L && r <= R){ mini[id].fi += val; laz[id] += val; return; } lazy(id); int mid = (l + r) >> 1; upd(id << 1, l, mid, L, R, val); upd(id << 1 | 1, mid + 1, r, L, R, val); mini[id] = min(mini[id << 1], mini[id << 1 | 1]); } void er(int id, int l, int r, int pos){ if(l == r){ mini[id].fi = oo; return; } lazy(id); int mid = (l + r) >> 1; if(pos <= mid) er(id << 1, l, mid, pos); else er(id << 1 | 1, mid + 1, r, pos); mini[id] = min(mini[id << 1], mini[id << 1 | 1]); } ii get(int id, int l, int r, int L, int R){ if(l > R || r < L) return {oo, oo}; if(l >= L && r <= R) return mini[id]; lazy(id); int mid = (l + r) >> 1; return min(get(id << 1, l, mid, L, R), get(id << 1 | 1, mid + 1, r, L, R)); } int b[N]; void init(int k, vector<int> r){ k--; int n = r.size(); for(int i = 0; i < n; i++) a[i] = k - r[i]; build(1, 0, n - 1); for(int i = 0; i < n; i++){ int temp = mini[1].se; ii temp2 = get(1, 0, n - 1, temp + k, n - 1); if(!temp2.fi) temp = temp2.se; if(temp == oo) assert(0); //cout << i << " " << temp << "\n"; b[temp] = i; //cout << temp << " " << i << "\n"; er(1, 0, n - 1, temp); //assert(get(1, 0, n - 1) == oo); upd(1, 0, n - 1, max(0, temp - k), temp - 1, -1); //cout << max(0, temp - k) << " " << temp - 1 << '\n'; if(temp < k){ upd(1, 0, n - 1, n + temp - k, n - 1, -1); //cout << n + temp - k << " " << n - 1 << "\n"; } } } int compare_plants(int x, int y){ if(b[x] < b[y]) return -1; if(b[x] > b[y]) return 1; return 0; } #ifdef local void process(){ } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); process(); } #endif
#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...