제출 #354341

#제출 시각아이디문제언어결과실행 시간메모리
354341ryansee식물 비교 (IOI20_plants)C++14
0 / 100
71 ms6764 KiB
#include "plants.h" #include "bits/stdc++.h" using namespace std; #define FAST ios_base::sync_with_stdio(false); cin.tie(0); #define pb push_back #define eb emplace_back #define ins insert #define f first #define s second #define cbr cerr<<"hi\n" #define mmst(x, v) memset((x), v, sizeof ((x))) #define siz(x) ll(x.size()) #define all(x) (x).begin(), (x).end() #define lbd(x,y) (lower_bound(all(x),y)-x.begin()) #define ubd(x,y) (upper_bound(all(x),y)-x.begin()) mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng) inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusivesss string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); } using ll=long long; using ld=long double; #define FOR(i,s,e) for(ll i=s;i<=ll(e);++i) #define DEC(i,s,e) for(ll i=s;i>=ll(e);--i) using pi=pair<ll,ll>; using spi=pair<ll,pi>; using dpi=pair<pi,pi>; long long LLINF = 1e18; int INF = 1e9+1e6; #define MAXN (200002) int n, start, k; vector<int> R; ll A[MAXN]; int dp[2][MAXN], dp2[2][MAXN]; inline ll cy(ll x) { x %= n, x += n, x %= n; return x; } vector<int> v[306]; bitset<306> reach[306]; ll dist(int x,int y) { if(x > y) swap(x, y); return min(y-x, n-y+x); } struct node { int s,e,m; spi v; ll lazy[3]; node*l,*r; node(int S,int E){ s=S,e=E,m=(s+e)>>1; v=spi(LLINF, pi(0, -1)), mmst(lazy, 0); if(s^e)l=new node(s,m),r=new node(m+1,e),v=min(l->v,r->v); else v=spi(R[s], pi(0, s)); } void value() { v.f += lazy[0], v.s.f += lazy[1]; if(s^e) FOR(i,0,1) l->lazy[i]+=lazy[i], r->lazy[i]+=lazy[i]; lazy[0]=lazy[1]=0; } void update(int x,int y,pi nval) { if(s==x&&e==y) { if(nval.s <= 1) lazy[nval.s] += nval.f; else lazy[nval.s] = max(lazy[nval.s], nval.f); return; } if(x>m) r->update(x,y,nval); else if(y<=m) l->update(x,y,nval); else l->update(x,m,nval),r->update(m+1,y,nval); l->value(), r->value(); v=min(l->v,r->v); } spi rmq(int x,int y) { value(); if(s==x&&e==y) return v; if(x>m) return r->rmq(x,y); else if(y<=m) return l->rmq(x,y); else return min(l->rmq(x,m),r->rmq(m+1,y)); } void set(int x,ll add=0) { value(); add = max(add, lazy[2]); if(s==e) { A[s] = add; v = spi(LLINF, pi(0, -1)); return; } if(x>m) r->set(x, add); else l->set(x, add); l->value(), r->value(); v = min(l->v, r->v); } } *seg; void update(int x,int y,pi nval) { x=cy(x), y=cy(y); if(x<=y) seg->update(x,y,nval); else seg->update(x,n-1,nval), seg->update(0,y,nval); } spi rmq(int x,int y) { x=cy(x), y=cy(y); if(x<=y) return seg->rmq(x, y); else return min(seg->rmq(x, n-1), seg->rmq(0, y)); } struct fen { ll fw[MAXN]; fen() { mmst(fw, 0); } void update(int x,ll nval) { ++ x; for(;x<MAXN;x+=x&(-x)) fw[x]+=nval; } ll sum(int x) { ++ x; ll res=0; for(;x;x-=x&(-x)) res+=fw[x]; return res; } ll sum(int a,int b) { return sum(b) - sum(a-1); } } fw[2]; void init(int K, std::vector<int> r) { k=K, R=r; n=r.size(); seg=new node(0, n-1); FOR(i,0,n-1) if(r[i]==0) update(i+1, i+k-1, pi(1, 1)); while(1) { start = -1; // FOR(i,0,n-1) if(!gone[i] && r[i] == 0) { // DEC(jj,i-1,i-k+1) { // int j = (jj + n) % n; // if(!gone[j] && r[j] == 0) goto no; // } // start = i; // break; // no:; // } start = seg->rmq(0, n-1).s.s; if(start == -1) break; // gone[start] = 1; seg->set(start); // FOR(i,start+1,start+k-1) if(!gone[i%n]) { // A[i%n]=max(A[i%n], A[start]+1); // } update(start+1, start+k-1, pi(A[start]+1, 2)); update(start+1, start+k-1, pi(-1, 1)); // FOR(i,start-k+1,start-1) if(!gone[(i+n)%n]) { // A[(i+n)%n] = max(A[(i+n)%n], A[start]+1), -- r[(i+n)%n]; // } update(start-k+1, start-1, pi(A[start]+1, 2)); update(start-k+1, start-1, pi(-1, 0)); vector<int> tmp; while(1) { spi x = rmq(start-k+1, start-1); if(x.f == 0) { tmp.eb(x.s.s); update(x.s.s+1, x.s.s+k-1, pi(1, 1)); update(x.s.s, x.s.s, pi(1, 0)); } else break; } for(auto i:tmp) update(i, i, pi(-1, 0)); } // FOR(i,0,n-1) assert(r[i]==0); if(n <= 300) { FOR(i,0,n-1) { FOR(jj,i+1,i+k-1) { int j=cy(jj); if(A[i] > A[j]) { v[i].eb(j); } else { v[j].eb(i); } } } function<void(ll,ll)>dfs=[&](ll x,ll o){ if(reach[o][x]) return; reach[o][x]=1; for(auto i:v[x]) dfs(i, o); }; FOR(i,0,n-1) dfs(i, i); } dp[0][0]=dp[1][0]=1; FOR(i,0,1) fw[i].update(A[i], 1); FOR(i,1,n-1) { // FOR(jj,i-k+1,i-1) { int j=cy(jj); // assert(A[i] ^ A[j]); // if(A[i] < A[j]) dp[0][i] |= dp[0][j]; // else dp[1][i] |= dp[1][j]; // } if(i >= k) FOR(j,0,1) if(dp[j][i-k]) fw[j].update(A[i-k], -1); dp[0][i] = fw[0].sum(A[i]+1, MAXN-2) > 0; dp[1][i] = fw[1].sum(0, A[i]-1) > 0; FOR(j,0,1) if(dp[j][i]) fw[j].update(A[i], 1); } dp2[0][0]=dp2[1][0]=1; DEC(ii,0,-n+1) { int i=cy(ii); FOR(jj,i+1,i+k-1) { int j=cy(jj); assert(A[i] ^ A[j]); if(A[i] < A[j]) dp2[0][i] |= dp2[0][j]; else dp2[1][i] |= dp2[1][j]; } } } int compare_plants(int x, int y) { if(x == 0) { if(dp[0][y] || dp2[0][y]) return -1; else if(dp[1][y] || dp2[1][y]) return 1; else return 0; } if(n > 300 || reach[x][y] || reach[y][x]) return A[x] < A[y] ? 1 : -1; else 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...