Submission #1050059

#TimeUsernameProblemLanguageResultExecution timeMemory
1050059fuad27Comparing Plants (IOI20_plants)C++17
25 / 100
248 ms49728 KiB
#include "plants.h" #include <bits/stdc++.h> using namespace std; struct lazy_segtree { vector<pair<int,int>> T; vector<int> lz; int n; void build(vector<int> &a, int tl, int tr, int v) { if(tl == tr) { T[v] = {a[tl], tl}; return; } int tm = (tl+tr)/2; build(a, tl, tm, 2*v); build(a, tm+1, tr, 2*v+1); T[v] = min(T[2*v], T[2*v+1]); } lazy_segtree(vector<int> &a) { n=a.size(); T.resize(4*n); lz.resize(4*n); build(a, 0, n-1, 1); } void push(int v){ lz[2*v] += lz[v]; lz[2*v+1] += lz[v]; T[2*v].first += lz[v]; T[2*v+1].first += lz[v]; lz[v] = 0; } void update(int l, int r, int add, int tl, int tr, int v) { if(r < tl or tr < l)return; if(l <= tl and tr<=r) { lz[v]+=add; T[v].first+=add; return; } push(v); int tm=(tl+tr)/2; update(l, r, add, tl, tm, 2*v); update(l, r, add, tm+1, tr, 2*v+1); T[v] = min(T[2*v], T[2*v+1]); } pair<int,int> query(int l, int r, int tl, int tr, int v) { if(r < tl or tr < l)return {1e9, 1e9}; if(l <= tl and tr<=r)return T[v]; push(v); int tm=(tl+tr)/2; return min(query(l, r, tl, tm, 2*v), query(l, r, tm+1, tr, 2*v+1)); } void update(int l, int r, int add) { update(l, r, add, 0, n-1, 1); } pair<int,int> query(int l, int r) { return query(l, r, 0, n-1, 1); } }; const int N = 2e5+10; vector<int> H; vector<int> g[N]; const int lg = 20; int sml[N][lg], grt[N][lg]; int k; int n; void init(int K, std::vector<int> r) { k=K; n = r.size(); lazy_segtree ls(r); int cnt = n; H.resize(n, -1); auto dfs = [&](int at, auto &&dfs) -> void { if(at >= k-1) { pair<int,int> val = ls.query(at-k+1, at-1); while(val.first == 0) { dfs(val.second, dfs); val = ls.query(at-k+1, at-1); } H[at] = cnt--; ls.update(at-k+1, at-1, -1); ls.update(at, at, 1e9); } else { pair<int,int> val = min(ls.query(0, at-1), ls.query(n-k+at+1, n-1)); while(val.first == 0) { dfs(val.second, dfs); val = min(ls.query(0, at-1), ls.query(n-k+at+1, n-1)); } H[at] = cnt--; ls.update(0, at-1, -1), ls.update(n-k+at+1, n-1, -1); ls.update(at, at, 1e9); } }; while(ls.query(0, n-1).first == 0) { dfs(ls.query(0, n-1).second, dfs); } for(int i = 0;i<n;i++) { H.push_back(H[i]); } // for(int i =0 ;i<2*n;i++) { // int nxtmn = -1; // for(int j = i+1;j<min(2*n, i+k);j++) { // if(H[j] < H[i] and (nxtmn == -1 or H[nxtmn] < H[j])) { // nxtmn = j; // } // } // sml[i][0] = nxtmn; // nxtmn = -1; // for(int j = i+1;j<min(2*n, i+k);j++) { // if(H[j] > H[i] and (nxtmn == -1 or H[nxtmn] > H[j])) { // nxtmn = j; // } // } // grt[i][0] = nxtmn; // } set<pair<int,int>> s; s.insert({-1e9, 2*n}); s.insert({1e9, 2*n}); for(int i = 2*n-1;i>=0;i--) { if(i+k < 2*n) { s.erase({H[i+k], i+k}); } grt[i][0] = (*s.lower_bound(pair{H[i], i})).second; sml[i][0] = (*(--s.lower_bound(pair{H[i], i}))).second; s.insert({H[i], i}); } for(int i =0 ;i<2*n;i++) { if(grt[i][0] == -1)grt[i][0]=2*n; if(sml[i][0] == -1)sml[i][0]=2*n; } sml[2*n][0] = grt[2*n][0] = 2*n; for(int i = 1;i<lg;i++) { for(int j = 0;j<=2*n;j++) { sml[j][i] = sml[sml[j][i-1]][i-1]; grt[j][i] = grt[grt[j][i-1]][i-1]; } } return; } int dist(int a, int b) { return min({abs(a-b), abs(a+n-b), abs(b+n-a)}); } int compare_plants(int x, int y) { { int a = x, b = y; if(b < a)b+=n; if(a+k-1 < b) { for(int i = lg-1;i>=0;i--) { if(grt[a][i] + k - 1 < b) { a=grt[a][i]; } } a=grt[a][0]; } if(a!=2*n and H[a]<H[b])return -1; a=x; if(a+k-1 < b) { for(int i = lg-1;i>=0;i--) { if(sml[a][i] + k - 1 < b) { a=sml[a][i]; } } a=sml[a][0]; } if(a!=2*n and H[a]>H[b])return 1; } { int a = y, b = x; if(b<a)b+=n; if(a+k-1 < b) { for(int i = lg-1;i>=0;i--) { if(grt[a][i] + k - 1 < b) { a=grt[a][i]; } } a=grt[a][0]; } if(a!=2*n and H[a]<H[b])return 1; a=y; if(a+k-1 < b) { for(int i = lg-1;i>=0;i--) { if(sml[a][i] + k - 1 < b) { a=sml[a][i]; } } a=sml[a][0]; } if(a!=2*n and H[a]>H[b])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...