제출 #807736

#제출 시각아이디문제언어결과실행 시간메모리
807736I_Love_EliskaM_식물 비교 (IOI20_plants)C++17
60 / 100
728 ms51168 KiB
#include "plants.h" #include <bits/stdc++.h> using namespace std; #define forn(i,_n) for(int i=0;i<_n;++i) #define all(x) x.begin(),x.end() #define pb push_back #define pi pair<int,int> #define f first #define s second using ll = long long; const int N=2e5+55; int p[N], L[N], R[N]; int n; int k; struct sgt { vector<pi> t; vector<int> lazy; int sz=1; pi merge(pi a, pi b) { if (a.f > b.f) return a; return b; } sgt(int n) { while (sz<n) sz<<=1; t.assign(2*sz,{0,n}); forn(i,n) t[sz-1+i]={0,i}; lazy.assign(4*sz,0); } void push(int v) { t[v].f+=lazy[v]; lazy[2*v+1]+=lazy[v]; lazy[2*v+2]+=lazy[v]; lazy[v]=0; } void add(int v, int l, int r, int lx, int rx, int x) { if (lazy[v]) push(v); if (rx<=l || r<=lx) return; if (lx<=l && r<=rx) { lazy[v]+=x; push(v); return; } int m=(l+r)>>1; add(2*v+1,l,m,lx,rx,x); add(2*v+2,m,r,lx,rx,x); t[v]=merge(t[2*v+1],t[2*v+2]); } void add(int l, int r, int x) { add(0,0,sz,l,r,x); } pi query(int v, int l, int r, int lx, int rx) { if (lazy[v]) push(v); if (rx<=l || r<=lx) return {-2e9,n}; if (lx<=l && r<=rx) return t[v]; int m=(l+r)>>1; auto lq=query(2*v+1,l,m,lx,rx); auto rq=query(2*v+2,m,r,lx,rx); t[v]=merge(t[2*v+1],t[2*v+2]); return merge(lq,rq); } pi query(int l, int r) { return query(0,0,sz,l,r); } }; sgt st(N); vector<int> adj[305]; int vis[305]; bitset<305> bs[305]; void dfs(int u) { if (vis[u]==1) assert(0); if (vis[u]) return; bs[u][u]=1; vis[u]=1; for(auto&v:adj[u]) { dfs(v); bs[u]|=bs[v]; } vis[u]=2; } void init(int _k, vector<int> r) { k=_k; n=r.size(); if (n<=300) { forn(i,n) r[i]=k-1-r[i]; forn(i,n) r.pb(r[i]); forn(i,n) r.pb(r[i]); forn(it,n) { for (int i=n; i<2*n; ++i) { if (r[i]==k-1) { int z=i; for (int j=i; j>z-k; --j) if (r[j]==k-1) z=j; for (int j=z+1; j<z+k; ++j) { if (vis[j%n]) adj[j%n].pb(z%n); else adj[z%n].pb(j%n); } vis[z%n]=1; r[z%n]=-1e9; for (int j=z; j>z-k; --j) { r[(j%n)]++; r[(j%n)+n]++; r[(j%n)+2*n]++; } break; } } } forn(i,n) vis[i]=0; forn(i,n) dfs(i); return; } if (k==2) { int z=0; forn(i,n) r[i]^=1; forn(i,n) if (r[i]==0) z=i; for (int i=z+n; i>z; --i) { if (r[i%n]) R[i%n]=R[(i+1)%n]; else R[i%n]=i%n; } z=0; forn(i,n) if (r[i]) z=i; ++z; for (int i=z; i<z+n; ++i) { if (r[(i-1+n)%n]) L[i%n]=i%n; else L[i%n]=L[(i-1+n)%n]; } forn(i,n) { L[i]+=n, R[i]+=n; } forn(i,n) { if (L[i]==R[i] && L[i]==i+n) continue; if (L[i]>=R[i]) L[i]-=n; } return; } forn(i,n) r.pb(r[i]); forn(i,n) r.pb(r[i]); sgt st(n); forn(i,n) st.add(i,i+1,r[i]); int z; for (int i=n; i<2*n; ++i) { if (r[i]==k-1) { z=i; for (int j=i; j>z-k; --j) if (r[j]==k-1) z=j; break; } } set<int> s; set<int> ok; int ri=-1; for (int l=z; l<z+n; ++l) { if (r[l]==k-1) { s.insert(l%n); s.insert(l%n+n); s.insert(l%n+2*n); if (l>=ri) { ok.insert(l%n); } ri=l+k; } } int nxt=1; forn(it,n) { auto x=*ok.begin(); ok.erase(ok.begin()); p[x]=nxt++; s.erase(x); s.erase(x+n); s.erase(x+2*n); st.add(x,x+1,-1e9); int j=x; if (s.size()) { auto it1=s.lower_bound(x); j=*it1; } j%=n; if (x-k+1>=0) { st.add(x-k+1,x,1); } else { st.add(0,x,1); st.add(x-k+1+n,n,1); } vector<int> v; while(1) { pi q; if (x-k+1>=0) { q=st.query(x-k+1,x); } else { auto q1=st.query(0,x); auto q2=st.query(x-k+1+n,n); q=st.merge(q1,q2); } if (q.f<k-1) break; if (q.s > j) { j+=n; } if (j-q.s>=k) { ok.insert(j%n); } j=q.s; s.insert(j); s.insert(j+n); s.insert(j+2*n); st.add(j,j+1,-1e9); v.pb(j); } if (!s.size()) break; for(auto&x:v) st.add(x,x+1,1e9); auto it2 = s.find(j+n); --it2; int t = *it2; if (j+n-t>=k) ok.insert(j); } } int compare_plants(int x, int y) { if (n<=300) { if (bs[x][y]) { return 1; } if (bs[y][x]) { return -1; } return 0; } if (k==2) { if (L[x]<=y && y<=R[x]) return 1; if (L[x]<=y+n && y+n<=R[x]) return 1; swap(x,y); if (L[x]<=y && y<=R[x]) return -1; if (L[x]<=y+n && y+n<=R[x]) return -1; return 0; } if (p[x]>p[y]) return 1; else return -1; }

컴파일 시 표준 에러 (stderr) 메시지

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:161:19: warning: 'z' may be used uninitialized in this function [-Wmaybe-uninitialized]
  161 |  for (int l=z; l<z+n; ++l) {
      |                  ~^~
#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...