Submission #357774

#TimeUsernameProblemLanguageResultExecution timeMemory
357774dooweyComparing Plants (IOI20_plants)C++14
100 / 100
2787 ms94136 KiB
#include <bits/stdc++.h> #include "plants.h" using namespace std; typedef long long ll; typedef pair<int,int> pii; #define fi first #define se second #define mp make_pair const int N = (int)2e5 + 100; int A[N]; int vl[N]; struct Node{ pii valid; // = r + vl pii zero; // = r int rlazy; int vllazy; }; Node T[N * 4 + 512]; void push(int node, int cl, int cr){ T[node].valid.fi += T[node].rlazy + T[node].vllazy; T[node].zero.fi += T[node].rlazy; if(cl != cr){ T[node*2].rlazy += T[node].rlazy; T[node*2+1].rlazy += T[node].rlazy; T[node*2].vllazy += T[node].vllazy; T[node*2+1].vllazy += T[node].vllazy; } T[node].rlazy = 0; T[node].vllazy = 0; } void upd(int node, int cl, int cr, int tl, int tr, int typ, int v){ push(node, cl, cr); if(cr < tl || cl > tr) return; if(cl >= tl && cr <= tr){ if(typ == 0) T[node].rlazy = v; else T[node].vllazy = v; push(node, cl, cr); return; } int mid = (cl + cr) / 2; upd(node * 2, cl, mid, tl, tr, typ, v); upd(node * 2 + 1, mid + 1, cr, tl, tr, typ, v); T[node].valid = min(T[node*2].valid, T[node*2+1].valid); T[node].zero = min(T[node*2].zero, T[node*2+1].zero); } pii get(int node, int cl, int cr, int tl, int tr, int ta){ push(node, cl, cr); if(cr < tl || cl > tr) return mp((int)1e9, (int)1e9); if(cl >= tl && cr <= tr){ if(ta == 0) return T[node].zero; else return T[node].valid; } int mid = (cl + cr) / 2; return min(get(node * 2, cl, mid, tl, tr, ta), get(node * 2 + 1, mid + 1, cr, tl, tr, ta)); } vector<int> r; void build(int node, int cl, int cr){ if(cl == cr){ T[node].valid = mp(r[cl], cl); T[node].zero = mp(r[cl], cl); return; } int mid = (cl + cr) / 2; build(node * 2, cl, mid); build(node * 2 + 1, mid + 1, cr); T[node].valid = min(T[node * 2].valid, T[node * 2 + 1].valid); T[node].zero = min(T[node * 2].zero, T[node * 2 + 1].zero); } int n, k; void upd_zero(int ii, int sign){ int nx = (ii + k - 1) % n; if(nx > ii){ upd(1, 0, n - 1, ii + 1, nx, 1, sign); } else{ upd(1, 0, n - 1, ii + 1, n - 1, 1, sign); upd(1, 0, n - 1, 0, nx, 1, sign); } } vector<int> getz(int li, int ri){ vector<int> soln; pii cc; while(li <= ri){ cc = get(1, 0, n - 1, li, ri, 0); if(cc.fi != 0) return soln; soln.push_back(cc.se); li = cc.se + 1; } return soln; } const int LOG = 18; int lef[LOG][N]; int rig[LOG][N]; int cl[LOG][N]; int cr[LOG][N]; void init(int k_, vector<int> r_) { r = r_; k = k_; n = r.size(); build(1, 0, n - 1); for(int i = 0 ; i < n; i ++ ){ if(r[i] == 0){ upd_zero(i,+1); } } int st; int pv; int nx; for(int id = n - 1; id >= 0 ; id -- ){ st = T[1].valid.se; A[st] = id; pv = (st - (k - 1) + n) % n; upd(1, 0, n - 1, st, st, 0, (int)1e9); upd_zero(st,-1); vector<int> nwz, cc; if(pv < st){ upd(1, 0, n - 1, pv, st - 1, 0, -1); cc = getz(pv, st - 1); for(auto q : cc) nwz.push_back(q); } else{ upd(1, 0, n - 1, 0, st - 1, 0, -1); upd(1, 0, n - 1, pv, n - 1, 0, -1); cc = getz(0, st - 1); for(auto q : cc) nwz.push_back(q); cc = getz(pv, n - 1); for(auto q : cc) nwz.push_back(q); } for(auto x : nwz){ upd_zero(x,+1); } } multiset<pii> alx; for(int i = n - 1; i >= n - (k - 1); i -- ){ alx.insert(mp(A[i], i)); } for(int i = 0 ; i < n; i ++ ){ auto it = alx.lower_bound(mp(A[i],-1)); if(it == alx.begin()){ lef[0][i] = -1; } else{ it -- ; cl[0][i] = (it->se > i); lef[0][i] = it->se; } pv = (i - (k - 1) + n) % n; alx.erase(mp(A[pv], pv)); alx.insert(mp(A[i],i)); } alx.clear(); for(int i = 1; i < k ; i ++ ){ alx.insert(mp(A[i],i)); } for(int i = 0; i < n; i ++ ){ auto it = alx.lower_bound(mp(A[i],-1)); if(it == alx.begin()){ rig[0][i] = -1; } else{ it -- ; cr[0][i] = (it->se < i); rig[0][i] = it->se; } if(i < n){ alx.erase(mp(A[i + 1], i + 1)); alx.insert(mp(A[(i + k) % n], (i + k) % n)); } } for(int lg = 1; lg < LOG; lg ++ ){ for(int i = 0 ; i < n; i ++ ){ lef[lg][i]=rig[lg][i]=-1; if(lef[lg-1][i] != -1){ lef[lg][i]=lef[lg-1][lef[lg-1][i]]; cl[lg][i] = (cl[lg-1][i] | cl[lg-1][lef[lg-1][i]]); } if(rig[lg-1][i] != -1){ rig[lg][i]=rig[lg-1][rig[lg-1][i]]; cr[lg][i] = (cr[lg-1][i] | cr[lg-1][rig[lg-1][i]]); } } } } int compare_plants(int x, int y) { int go = x; for(int i = LOG - 1; i >= 0 ; i -- ){ if(lef[i][go] != -1 && cl[i][go] != 1) go = lef[i][go]; } if(lef[0][go] != -1){ if(lef[0][go] > y){ go = lef[0][go]; for(int i = LOG - 1; i >= 0 ; i -- ){ if(lef[i][go] != -1 && cl[i][go] != 1 && lef[i][go] > y) go = lef[i][go]; } if((go - y + n) % n < k){ if(A[go] > A[y]) return +1; } } else{ if(A[go] > A[y]) return +1; } } go = x; for(int i = LOG - 1; i >= 0 ; i -- ){ if(rig[i][go] != -1 && cr[i][go] != 1 && rig[i][go] < y){ go = rig[i][go]; } } if(y - go < k){ if(A[go] > A[y]) return +1; } // go = y; for(int i = LOG - 1; i >= 0 ; i -- ){ if(lef[i][go] != -1 && cl[i][go] != 1 && lef[i][go] > x){ go = lef[i][go]; } } if(go - x < k){ if(A[go] > A[x]) return -1; } // go = y; for(int i = LOG - 1; i >= 0 ; i -- ){ if(rig[i][go] != -1 && cr[i][go] != 1) go = rig[i][go]; } if(rig[0][go] != -1){ if(rig[0][go] < x){ for(int i = LOG - 1; i >= 0 ; i -- ){ if(rig[i][go] != -1 && cr[i][go] != 1 && cr[i][go] < x){ go = rig[i][go]; } } if(x - go < k){ if(A[go] > A[x]) return -1; } } else{ if(A[go] > A[x]) return -1; } } return 0; }

Compilation message (stderr)

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:129:9: warning: unused variable 'nx' [-Wunused-variable]
  129 |     int nx;
      |         ^~
#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...