Submission #434630

#TimeUsernameProblemLanguageResultExecution timeMemory
434630frodakcinComparing Plants (IOI20_plants)C++11
14 / 100
4046 ms8996 KiB
#include "plants.h" #include <queue> #include <bitset> template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;} template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;} const int MN = 2e5+10; const int INF = 0x3f3f3f3f; int N, K, ctr, ord[MN]; bool v[MN]; //Minmax Segtree struct minmax { public: int min, max; minmax(int _mn=INF, int _mx=-INF): min(_mn), max(_mx) {} minmax& operator += (const int& o) {min += o, max += o; return *this;} minmax& operator -= (const int& o) {min -= o, max -= o; return *this;} minmax& operator += (const minmax& o) {ckmin(min, o.min); ckmax(max, o.max); return *this;} friend minmax operator + (minmax a, const int& b) {return a+=b;} friend minmax operator - (minmax a, const int& b) {return a-=b;} friend minmax operator + (minmax a, const minmax& b) {return a+=b;} bool contains(int x) {return min <= x && x <= max;} } range[MN]; minmax mv[1 << 19]; minmax mqry(int n, int l, int r, int ql, int qr) { if(ql <= l && r <= qr) return mv[n]; else { int m=l+(r-l)/2; minmax f; if(ql < m) f += mqry(n<<1, l, m, ql, qr); if(m < qr) f += mqry(n<<1|1, m, r, ql, qr); return r; } } void mupd(int n, int l, int r, int q, minmax val) { if(r-l>1) { int m=l+(r-l)/2; if(q < m) mupd(n<<1, l, m, q, val); else mupd(n<<1|1, m, r, q, val); mv[n]=mv[n<<1]+mv[n<<1|1]; } else mv[n]=val; } void init(int k, std::vector<int> r) { K=k, N=r.size(); std::queue<int> q; int zc=0; for(int i=N-K;i<N;++i) zc += !r[i]; for(int i=0;i<N;++i) { zc -= !r[(N-K+i)%N]; if(zc==0 && r[i]==0) q.push(i); zc += !r[i]; } for(;!q.empty();) { int n=q.front(); q.pop(); if(r[n] < 0) continue; // check bool ok=1; for(int i=1;i<K;++i) if(r[(n-i+N)%N]==0) ok=0; if(!ok) continue; // add r[n]=-1; for(int i=K-1;i>0;--i) --r[(n-i+N)%N]; for(int i=1;i<K;++i) if(r[(n+i)%N] == 0) { q.push((n+i)%N); break; } for(int i=K-1;i>0;--i) if(r[(n-i+N)%N] == 0) { q.push((n-i+N)%N); break; } //modify ans ord[n]=ctr++; range[n] = minmax(n-K+1, n+K-1); range[n] += mqry(1, 0, N, n-K+1, n+K); if(n+K>N) range[n] += mqry(1, 0, N, 0, n+K-N)+N; if(n-K+1<0) range[n] += mqry(1, 0, N, n-K+1+N, N)-N; mupd(1, 0, N, n, range[n]); //printf("%d: %d <-> %d\n", n, range[n].min, range[n].max); } return; } bool cover(int a, int b) { if(ord[a]>ord[b]) return 0; return range[a].contains(b) || range[a].contains(b+N) || range[a].contains(b-N); } int compare_plants(int x, int y) { if(cover(x, y)) return 1; if(cover(y, x)) return -1; 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...