제출 #301126

#제출 시각아이디문제언어결과실행 시간메모리
301126justtestingthis2식물 비교 (IOI20_plants)C++14
27 / 100
1055 ms25856 KiB
#include<bits/stdc++.h> #include "plants.h" #define lc (id << 1) #define rc (lc ^ 1) #define md ((l + r) >> 1) using namespace std; const int N = 200005; const int MXS = N * 4; int n, k, A[N], P[2][N], rev[2][N]; int wset; struct CMP { inline int operator() (int a, int b) const { if (!wset) return a < b; return rev[0][a] > rev[0][b]; }; }; queue < int > Todo; vector < int > res; struct SEGT { int MN[MXS], LZ[MXS]; int le, ri, val; inline void Reset() { memset(MN, 0, sizeof(MN)); memset(LZ, 0, sizeof(LZ)); } inline void Shift(int id) { MN[lc] += LZ[id]; MN[rc] += LZ[id]; LZ[lc] += LZ[id]; LZ[rc] += LZ[id]; LZ[id] = 0; return ; } void Adder(int id = 1, int l = 0, int r = n) { if (ri <= l || r <= le) return ; if (le <= l && r <= ri) { MN[id] += val; LZ[id] += val; return ; } Shift(id); Adder(lc, l, md); Adder(rc, md, r); MN[id] = min(MN[lc], MN[rc]); } inline void Add(int l, int r, int vl) { val = vl; if (l < 0) l += n, r += n; assert(r - n <= l); assert(l >= 0); if (r <= n) { le = l; ri = r; Adder(); } else { le = l; ri = n; Adder(); le = 0; ri = r - n; Adder(); } } void Extract(int id = 1, int l = 0, int r = n) { assert(MN[id] >= 0); if (MN[id] > 0) return ; if (r - l < 2) return void(res.push_back(l)); Shift(id); Extract(lc, l, md); Extract(rc, md, r); } }; pair < int , int > F[N]; SEGT SG[2]; /*bitset < N > Ad[N]; int Mark[N]; void DFS(int v) { Mark[v] = 1; for (int u = 0; u < n; u ++) if (Ad[v][u]) { if (!Mark[u]) DFS(u); Ad[v] |= Ad[u]; } }*/ int MN[N * 4], MX[N * 4]; int segn; inline void Do(int i, int av, int bv) { i += segn; if (av < 0) av += n, bv += n; MN[i] = av; MX[i] = bv; for (; i; i >>= 1) { MN[i >> 1] = min(MN[i], MN[i ^ 1]); MX[i >> 1] = max(MX[i], MX[i ^ 1]); } } inline pair < int , int > Get(int l, int r) { pair < int , int > ret = {l, r}; for (l += segn, r += segn; l < r; l >>= 1, r >>= 1) { if (l & 1) { ret.first = min(ret.first, MN[l]); ret.second = max(ret.second, MX[l]); l ++; } if (r & 1) { r --; ret.first = min(ret.first, MN[r]); ret.second = max(ret.second, MX[r]); } } if (ret.first < 0) ret.first += n, ret.second += n; if (ret.second >= ret.first + n) ret = {0, n}; return ret; } inline pair < int , int > Query(int le, int ri) { int mn = le; int mx = ri; assert(le >= 0 && ri <= n + n); assert(le >= 0); pair < int , int > ret = Get(le, ri); mn = min(mn, ret.first); mx = max(mx, ret.second); ret = Get(max(le - n, 0), max(ri - n, 0)); mn = min(mn, ret.first); mx = max(mx, ret.second); ret = Get(min(le + n, segn), min(ri + n, segn)); mn = min(mn, ret.first); mx = max(mx, ret.second); if (mn < 0) mn += n, mx += n; if (mn >= n) mn -= n, mx -= n; mx = min(mx, n + n); return make_pair(mn, mx); } void init(int _k, vector < int > _r) { k = _k; n = (int)_r.size(); for (int i = 0; i < n; i ++) A[i] = _r[i]; for (int w = 0; w <= 0; w ++) { wset = w; SG[0].Reset(); SG[1].Reset(); for (int i = 0; i < n; i ++) { if (A[i]) { SG[1].Add(i, i + 1, 1); SG[0].Add(i, i + 1, A[i]); } else { SG[1].Add(i + 1, i + k, 1); SG[0].Add(i, i + 1, N); } } vector < int > M(n, 0); for (int __ = 0; __ < n; __ ++) { res.clear(); SG[1].Extract(); for (int i : res) Todo.push(i); res.clear(); assert((int)Todo.size()); int i = Todo.front(); M[i] = 1; Todo.pop(); /*for (int j = i - k + 1; j < i + k; j ++) { int tt = j; if (tt < 0) tt += n; if (tt >= n) tt -= n; if (M[tt]) continue; Ad[tt][i] = 1; }*/ F[i] = {i - k + 1, i + k}; P[w][__] = i; rev[w][i] = __; SG[1].Add(i, i + 1, N); SG[0].Add(i - k + 1, i, -1); SG[1].Add(i + 1, i + k, -1); res.clear(); SG[0].Extract(); for (int j : res) { SG[1].Add(j, j + 1, -1); SG[1].Add(j + 1, j + k, 1); SG[0].Add(j, j + 1, N); } res.clear(); } /*for (int i = 0; i < n; i ++) printf("%d ", P[w][i]); printf("\n");*/ } /*for (int i = 0; i < n; i ++) if (!Mark[i]) DFS(i);*/ /* segn = n + n; memset(MN, 63, sizeof(MN)); memset(MX, -63, sizeof(MX)); for (int h = n - 1; h >= 0; h --) { int i = P[0][h]; // printf("=== %d :: %d , %d\n", i, F[i].first, F[i].second); if (F[i].first < 0) F[i].first += n, F[i].second += n; if (F[i].first >= n) F[i].first -= n, F[i].second -= n; F[i].second = min(F[i].second, segn); F[i] = Query(F[i].first, F[i].second); if (F[i].first < 0) F[i].first += n, F[i].second += n; if (F[i].first >= n) F[i].first -= n, F[i].second -= n; F[i].second = min(F[i].second, segn); Do(i, F[i].first, F[i].second); Do(i + n, F[i].first, F[i].second); // printf("%d :: %d , %d\n", i, F[i].first, F[i].second); }*/ return ; /* for (int i = 0; i < n; i ++) { printf("%d :: %d\n", F[i].first, F[i].second); }*/ } inline bool Check(pair < int , int > ff, int i) { int l = ff.first; int r = ff.second; if (l < 0) l += n, r += n; if (l <= i && i < r) return 1; if (l <= i + n && i + n < r) return 1; return 0; } int compare_plants(int a, int b) { if (rev[0][a] < rev[0][b]) return 1; return -1; /*if (Ad[a][b]) return -1; if (Ad[b][a]) return 1; return 0;*/ if (rev[0][a] < rev[0][b] && Check(F[a], b)) return 1; if (rev[0][b] < rev[0][a] && Check(F[b], a)) 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...