제출 #528052

#제출 시각아이디문제언어결과실행 시간메모리
528052qwerasdfzxcl식물 비교 (IOI20_plants)C++14
100 / 100
1016 ms58868 KiB
#include "plants.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 1e9; int n, a[200200], idxa[200200]; struct Seg2{ pair<int, int> tree[800800]; int lazy[800800]; void init(int i, int l, int r){ lazy[i] = 0; if (l==r) {tree[i] = {INF, l}; return;} int m = (l+r)>>1; init(i<<1, l, m); init(i<<1|1, m+1, r); tree[i] = min(tree[i<<1], tree[i<<1|1]); } void propagate(int i, int l, int r){ tree[i].first += lazy[i]; if (l!=r) lazy[i<<1] += lazy[i], lazy[i<<1|1] += lazy[i]; lazy[i] = 0; } void update(int i, int l, int r, int s, int e, int x){ propagate(i, l, r); if (r<s || e<l) return; if (s<=l && r<=e){ lazy[i] += x; propagate(i, l, r); return; } int m = (l+r)>>1; update(i<<1, l, m, s, e, x); update(i<<1|1, m+1, r, s, e, x); tree[i] = min(tree[i<<1], tree[i<<1|1]); } void update2(int i, int l, int r, int s, int x){ propagate(i, l, r); if (r<s || s<l) return; if (l==r) {tree[i].second = x; return;} int m = (l+r)>>1; update2(i<<1, l, m, s, x); update2(i<<1|1, m+1, r, s, x); tree[i] = min(tree[i<<1], tree[i<<1|1]); } void update(int l, int r, int x){ if (r<=n) update(1, 1, n, l, r, x); else{ update(1, 1, n, l, n, x); update(1, 1, n, 1, r-n, x); } } }tree2; struct Seg1{ int tree[800800], lazy[800800]; void init(int i, int l, int r, vector<int> &vec){ lazy[i] = 0; if (l==r) {tree[i] = vec[l-1]; return;} int m = (l+r)>>1; init(i<<1, l, m, vec); init(i<<1|1, m+1, r, vec); tree[i] = max(tree[i<<1], tree[i<<1|1]); } void propagate(int i, int l, int r){ tree[i] += lazy[i]; if (l!=r) lazy[i<<1] += lazy[i], lazy[i<<1|1] += lazy[i]; lazy[i] = 0; } void update(int i, int l, int r, int s, int e, int x){ propagate(i, l, r); if (r<s || e<l) return; if (s<=l && r<=e){ lazy[i] += x; propagate(i, l, r); return; } int m = (l+r)>>1; update(i<<1, l, m, s, e, x); update(i<<1|1, m+1, r, s, e, x); tree[i] = max(tree[i<<1], tree[i<<1|1]); } void find(int i, int l, int r, int x){ propagate(i, l, r); if (tree[i]<x) return; if (l==r){ assert(tree[i]==x); //printf("YES: %d\n", l); tree2.update(l, l, -INF); tree2.update(l+1, l+x, 1); update(1, 1, n, l, l, -INF); return; } int m = (l+r)>>1; find(i<<1, l, m, x); find(i<<1|1, m+1, r, x); tree[i] = max(tree[i<<1], tree[i<<1|1]); } void update(int s, int e, int x){ if (s>0) update(1, 1, n, s, e, x); else{ update(1, 1, n, s+n, n, x); update(1, 1, n, 1, e, x); } } }tree1; struct Seg3{ pair<int, int> tree[400400]; int sz; void init(int n, int *a){ sz = n+1; for (int i=sz;i<sz*2;i++) tree[i] = {a[i-sz], i-sz}; for (int i=sz-1;i;i--) tree[i] = min(tree[i<<1], tree[i<<1|1]); } void update(int p, int x){ for (tree[p+=sz].first=x;p>1;p>>=1) tree[p>>1] = min(tree[p], tree[p^1]); } pair<int, int> query(int l, int r){ pair<int, int> ret = {INF, -1}; for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){ if (l&1) ret = min(ret, tree[l++]); if (r&1) ret = min(ret, tree[--r]); } return ret; } int queryc(int l, int r){ if (l<=0){ auto p = min(query(l+n, sz), query(1, r+1)); return p.second; } if (r>n){ auto p = min(query(l, sz), query(1, r-n+1)); return p.second; } return query(l, r+1).second; } }tree3; vector<int> r; int k, adj[200200][2][20], nxt[200200][2]; void init(int K, vector<int> R) { k = K, r = R; n = r.size(); tree1.init(1, 1, n, r); tree2.init(1, 1, n); tree2.update2(1, 1, n, 1, INF+1); for (int i=1;i<=n;i++){ tree1.find(1, 1, n, k-1); assert(tree2.tree[1].first==0); a[i] = tree2.tree[1].second; if (a[i]>=INF) a[i] -= INF; //printf("a[%d] = %d\n", i, a[i]); tree2.update(a[i], a[i], INF); tree2.update(a[i]+1, a[i]+k-1, -1); tree1.update(a[i]-k+1, a[i]-1, 1); } for (int i=1;i<=n;i++) idxa[a[i]] = i; //printf("idxa: "); //for (int i=1;i<=n;i++) printf("%d ", idxa[i]); //printf("\n"); tree3.init(n, idxa); for (int i=1;i<=n;i++){ int pos = a[i]; int l = tree3.queryc(pos-k+1, pos-1), r = tree3.queryc(pos+1, pos+k-1); adj[pos][0][0] = l, adj[pos][1][0] = r; nxt[pos][0] = nxt[pos][1] = -1; if (pos<l) adj[pos][0][0] = -1, nxt[pos][0] = l; if (pos>r) adj[pos][1][0] = -1, nxt[pos][1] = r; //printf("%d: %d %d %d %d\n", pos, adj[pos][0][0], adj[pos][1][0], nxt[pos][0], nxt[pos][1]); tree3.update(pos, INF+1); } for (int k=1;k<20;k++){ for (int i=1;i<=n;i++){ for (int j=0;j<2;j++){ if (adj[i][j][k-1]==-1) {adj[i][j][k] = -1; continue;} adj[i][j][k] = adj[adj[i][j][k-1]][j][k-1]; } } } } int dist(int x, int y){ if (x<y) return y - x; return n + y - x; } bool is_reachable(int x, int y){ int s = x; if (y<x){ for (int t=19;t>=0;t--) if (adj[s][1][t]!=-1) s = adj[s][1][t]; if (dist(s, y)<k && idxa[s] < idxa[y]) return 1; s = nxt[s][1]; } if (s!=-1){ for (int t=19;t>=0;t--) if (adj[s][1][t]!=-1 && adj[s][1][t] < y && dist(adj[s][1][t], y) >= k) s = adj[s][1][t]; if (s!=-1 && dist(s, y) >= k) s = adj[s][1][0]; if (s!=-1 && dist(s, y)<k && idxa[s] < idxa[y]) return 1; } s = x; if (x<y){ for (int t=19;t>=0;t--) if (adj[s][0][t]!=-1) s = adj[s][0][t]; if (dist(y, s)<k && idxa[s] < idxa[y]) return 1; s = nxt[s][0]; } if (s!=-1){ for (int t=19;t>=0;t--) if (adj[s][0][t]!=-1 && adj[s][0][t] > y && dist(y, adj[s][0][t]) >= k) s = adj[s][0][t]; if (s!=-1 && dist(y, s) >= k) s = adj[s][0][0]; if (s!=-1 && dist(y, s)<k && idxa[s] < idxa[y]) return 1; } return 0; } int compare_plants(int x, int y) { ++x, ++y; if (is_reachable(x, y)) return -1; if (is_reachable(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...