Submission #317627

#TimeUsernameProblemLanguageResultExecution timeMemory
317627arnold518Comparing Plants (IOI20_plants)C++14
11 / 100
1632 ms2097156 KiB
#include "plants.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 300; const int INF = 1e8; int N, K, R[MAXN+10], H[MAXN+10]; struct SEG { pii tree[MAXN*4+10]; int lazy[MAXN*4+10]; void busy(int node, int tl, int tr) { tree[node].first+=lazy[node]; if(tl!=tr) { lazy[node*2]+=lazy[node]; lazy[node*2+1]+=lazy[node]; } lazy[node]=0; } void init(int node, int tl, int tr) { if(tl==tr) { tree[node]={0, tl}; lazy[node]=0; return; } int mid=tl+tr>>1; init(node*2, tl, mid); init(node*2+1, mid+1, tr); tree[node]=min(tree[node*2], tree[node*2+1]); } void update(int node, int tl, int tr, int l, int r, int k) { busy(node, tl, tr); if(l<=tl && tr<=r) { lazy[node]+=k; busy(node, tl, tr); return; } if(r<tl || tr<l) return; int mid=tl+tr>>1; update(node*2, tl, mid, l, r, k); update(node*2+1, mid+1, tr, l, r, k); tree[node]=min(tree[node*2], tree[node*2+1]); } void update2(int node, int tl, int tr, int p, int k) { busy(node, tl, tr); if(tl==tr) { tree[node].first=k; return; } int mid=tl+tr>>1; if(p<=mid) update2(node*2, tl, mid, p, k); else update2(node*2+1, mid+1, tr, p, k); tree[node]=min(tree[node*2], tree[node*2+1]); } int query(int node, int tl, int tr, int l, int r) { busy(node, tl, tr); if(l<=tl && tr<=r) return tree[node].first; if(r<tl || tr<l) return INF; int mid=tl+tr>>1; return min(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r)); } void query2(int node, int tl, int tr, int l, int r, vector<int> &V) { busy(node, tl, tr); if(tree[node].first!=0) return; if(r<tl || tr<l) return; if(tl==tr) { V.push_back(tl); return; } int mid=tl+tr>>1; query2(node*2, tl, mid, l, r, V); query2(node*2+1, mid+1, tr, l, r, V); } void init() { init(1, 0, N-1); } void update(int l, int r, int k) { l=(l%N+N)%N; r=(r%N+N)%N; if(l<=r) update(1, 0, N-1, l, r, k); else { update(1, 0, N-1, l, N-1, k); update(1, 0, N-1, 0, r, k); } } void update2(int p, int k) { p=(p%N+N)%N; update2(1, 0, N-1, p, k); } int query(int l, int r) { l=(l%N+N)%N; r=(r%N+N)%N; if(l<=r) return query(1, 0, N-1, l, r); else return min(query(1, 0, N-1, l, N-1), query(1, 0, N-1, 0, r)); } vector<int> query2(int l, int r) { vector<int> ret; l=(l%N+N)%N; r=(r%N+N)%N; if(l<=r) query2(1, 0, N-1, l, r, ret); else { query2(1, 0, N-1, l, N-1, ret); query2(1, 0, N-1, 0, r, ret); } return ret; } }seg1, seg2; int adj[MAXN+10][MAXN+10]; void init(int _K, vector<int> _R) { K=_K; N=_R.size(); for(int i=0; i<N; i++) R[i]=_R[i]; seg1.init(); seg2.init(); for(int i=0; i<N; i++) { seg1.update2(i, R[i]); seg2.update2(i, R[i]); } for(int i=0; i<N; i++) if(R[i]==0) seg1.update(i+1, i+K-1, 1); for(int i=N-1; i>=0; i--) { vector<int> V; assert(seg1.tree[1].first+seg1.lazy[1]==0); int now=seg1.tree[1].second; H[now]=i; assert(seg2.query(now-K+1, now-1)>=1); seg1.update(now+1, now+K-1, -1); seg1.update2(now, INF); seg2.update2(now, INF); seg2.update(now-K+1, now-1, -1); seg1.update(now-K+1, now-1, -1); V=seg2.query2(now-K+1, now-1); for(auto it : V) { //printf("!%d\n", it); seg1.update(it+1, it+K-1, 1); } //for(int j=0; j<N; j++) printf("%d ", seg1.query(j, j)); printf(" : seg1\n"); //for(int j=0; j<N; j++) printf("%d ", seg2.query(j, j)); printf(" : seg2\n"); } //for(int i=0; i<N; i++) printf("%d ", H[i]); printf("\n"); for(int i=0; i<N; i++) for(int j=0; j<N; j++) adj[i][j]=INF; for(int i=0; i<N; i++) for(int j=1; j<K; j++) { int u=i, v=(i+j)%N; if(H[u]>H[v]) adj[u][v]=0; else adj[v][u]=0; } for(int k=0; k<N; k++) for(int i=0; i<N; i++) for(int j=0; j<N; j++) adj[i][j]=min(adj[i][j], adj[i][k]+adj[k][j]); return; } int compare_plants(int x, int y) { int ans=0; if(adj[x][y]==0) return 1; if(adj[y][x]==0) return -1; return 0; }

Compilation message (stderr)

plants.cpp: In member function 'void SEG::init(int, int, int)':
plants.cpp:37:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |   int mid=tl+tr>>1;
      |           ~~^~~
plants.cpp: In member function 'void SEG::update(int, int, int, int, int, int)':
plants.cpp:52:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |   int mid=tl+tr>>1;
      |           ~~^~~
plants.cpp: In member function 'void SEG::update2(int, int, int, int, int)':
plants.cpp:65:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |   int mid=tl+tr>>1;
      |           ~~^~~
plants.cpp: In member function 'int SEG::query(int, int, int, int, int)':
plants.cpp:75:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |   int mid=tl+tr>>1;
      |           ~~^~~
plants.cpp: In member function 'void SEG::query2(int, int, int, int, int, std::vector<int>&)':
plants.cpp:88:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |   int mid=tl+tr>>1;
      |           ~~^~~
plants.cpp: In function 'int compare_plants(int, int)':
plants.cpp:184:6: warning: unused variable 'ans' [-Wunused-variable]
  184 |  int ans=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...