Submission #589735

#TimeUsernameProblemLanguageResultExecution timeMemory
589735LucppComparing Plants (IOI20_plants)C++17
49 / 100
970 ms33364 KiB
#include "plants.h" #include <bits/stdc++.h> using namespace std; const int INF = 1e8; int n, k; vector<int> dpL, dpR; void init_k2(vector<int> r){ dpL.resize(n), dpR.resize(n); for(int it = 0; it < 2; it++){ for(int i = n-1; i >= 0; i--){ if(r[i]) dpR[i] = dpR[(i+1)%n]+1; } for(int i = 0; i < n; i++){ if(!r[(i+n-1)%n]) dpL[i] = dpL[(i+n-1)%n]+1; } } } struct Data{ int m = INF, l, r, ind = -1; }; Data combine(Data a, Data b){ Data d; d.m = min(a.m, b.m); if(d.m == a.m) d.l = a.l; else d.l = b.l; if(d.m == b.m) d.r = b.r; else d.r = a.r; if(d.m == a.m && a.ind != -1) d.ind = a.ind; if(d.m == b.m && b.ind != -1) d.ind = b.ind; if(d.m == a.m && d.m == b.m && b.l-a.r >= k) d.ind = b.l; return d; } int cap; vector<Data> S; vector<int> O; vector<bool> lazy; void build(vector<int> v){ for(cap = 1; cap < (int)v.size(); cap *= 2); S.resize(2*cap); O.resize(2*cap); lazy.resize(2*cap); for(int i = 0; i < (int)v.size(); i++) S[i+cap] = Data{v[i], i+1, i+1}; for(int i = cap-1; i > 0; i--) S[i] = combine(S[2*i], S[2*i+1]); } void apply(int v, int i){ lazy[i] = true; O[i] += v; S[i].m += v; } void push(int i){ if(lazy[i]){ apply(O[i], 2*i); apply(O[i], 2*i+1); O[i] = 0; lazy[i] = false; } } void upd(int p, int v, int a, int b, int i){ if(a == b) S[i] = {v, p, p, -1}; else{ push(i); int m = (a+b)/2; if(p <= m) upd(p, v, a, m, 2*i); else upd(p, v, m+1, b, 2*i+1); S[i] = combine(S[2*i], S[2*i+1]); } } void apply(int l, int r, int v, int a, int b, int i){ if(l <= a && b <= r) apply(v, i); else if(b < l || r < a) return; else{ push(i); int m = (a+b)/2; apply(l, r, v, a, m, 2*i); apply(l, r, v, m+1, b, 2*i+1); S[i] = combine(S[2*i], S[2*i+1]); } } vector<int> h; void init_else(vector<int> r){ h.resize(2*n); r.resize(2*n); for(int i = 0; i < n; i++) r[i+n] = r[i]; build(r); for(int it = 0; it < n; it++){ assert(S[1].m == 0); assert(S[1].ind != -1); int i = S[1].ind; i = (i-1)%n; h[i] = h[i+n] = n-it; upd(i+1, INF, 1, cap, 1); upd(i+n+1, INF, 1, cap, 1); apply(max(0, i-k+1)+1, i, -1, 1, cap, 1); apply(i+n-k+2, i+n, -1, 1, cap, 1); apply(i+2*n-k+2, 2*n, -1, 1, cap, 1); } } void init(int K, vector<int> r) { k = K; n = (int)r.size(); if(k == 2) init_k2(r); else init_else(r); } int compare_k2(int x, int y){ int d1 = (y-x+n)%n; int d2 = n-d1; if(dpR[x] >= d1 || dpL[x] >= d2) return -1; if(dpR[y] >= d2 || dpL[y] >= d1) return 1; return 0; } int compare_else(int x, int y){ if(h[x] < h[y]) return -1; else return 1; } int compare_plants(int x, int y) { if(k == 2) return compare_k2(x, y); else return compare_else(x, y); }
#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...