Submission #452139

#TimeUsernameProblemLanguageResultExecution timeMemory
452139rainboyComparing Plants (IOI20_plants)C++17
44 / 100
1046 ms75328 KiB
#include "plants.h" #include <stdlib.h> #include <string.h> using namespace std; typedef vector<int> vi; const int N = 200000, LN = 18, N_ = 1 << LN, INF = 0x3f3f3f3f; /* LN = ceil(log2(N)) */ int min(int a, int b) { return a < b ? a : b; } int max(int a, int b) { return a > b ? a : b; } int aa[N], ii[N], n, k; int st[N_ * 2], lz[N_ * 2], first[N_ * 2], last[N_ * 2], gap[N_ * 2], n_; void put(int i, int x) { st[i] += x, lz[i] += x; } void pul(int i) { int l = i << 1, r = l | 1; if (st[l] < st[r]) st[i] = st[l], first[i] = first[l], last[i] = last[l], gap[i] = gap[l]; else if (st[l] > st[r]) st[i] = st[r], first[i] = first[r], last[i] = last[r], gap[i] = gap[r]; else st[i] = st[l], first[i] = first[l], last[i] = last[r], gap[i] = max(max(gap[l], gap[r]), first[r] - last[l]); st[i] += lz[i]; } void pull(int i) { while (i > 1) pul(i >>= 1); } void update(int l, int r, int x) { int l_ = l += n_, r_ = r += n_; for ( ; l <= r; l >>= 1, r >>= 1) { if ((l & 1) == 1) put(l++, x); if ((r & 1) == 0) put(r--, x); } pull(l_), pull(r_); } int get() { int i = 1; if (gap[1] < k) return first[1]; while (i < n_) if (st[i] == st[i << 1 | 0] + lz[i] && gap[i << 1 | 0] >= k) i = i << 1 | 0; else if (st[i] == st[i << 1 | 1] + lz[i] && gap[i << 1 | 1] >= k) i = i << 1 | 1; else return first[i << 1 | 1]; return -1; } void update_(int l, int r, int x) { for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) { if ((l & 1) == 1) st[l++] = x; if ((r & 1) == 0) st[r--] = x; } } int query_(int i) { int x = INF; for (i += n_; i > 0; i >>= 1) x = min(x, st[i]); return x; } char root[N]; int pp[2][LN + 1][N], dd[2][LN + 1][N]; void init(int k_, vi rr) { int h, h_, i, dir, l; n = rr.size(), k = k_; n_ = 1; while (n_ < n) n_ <<= 1; for (i = 0; i < n_; i++) { st[n_ + i] = i < n ? rr[i] : INF, gap[n_ + i] = 0; first[n_ + i] = last[n_ + i] = i; } for (i = n_ - 1; i > 0; i--) pul(i); for (h = n - 1; h >= 0; h--) { i = get(); aa[ii[h] = i] = h; update(i, i, INF); if (i >= k - 1) update(i - k + 1, i, -1); else update(0, i, -1), update(i - k + 1 + n, n - 1, -1); } memset(st, 0x3f, n_ * 2 * sizeof *st); for (h = n - 1; h >= 0; h--) { i = ii[h], h_ = query_(i); if (h_ == INF) root[i] = 1, pp[0][0][i] = -1; else root[i] = 0, pp[0][0][i] = ii[h_]; if (i >= k - 1) update_(i - k + 1, i, h); else update_(0, i, h), update_(i - k + 1 + n, n - 1, h); } memset(st, 0x3f, n_ * 2 * sizeof *st); for (h = n - 1; h >= 0; h--) { i = ii[h], h_ = query_(i); if (h_ == INF) root[i] = 1, pp[1][0][i] = -1; else root[i] = 0, pp[1][0][i] = ii[h_]; if (i + k - 1 < n) update_(i, i + k - 1, h); else update_(i, n - 1, h), update_(0, i + k - 1 - n, h); } for (dir = 0; dir < 2; dir++) { for (i = 0; i < n; i++) dd[dir][0][i] = pp[dir][0][i] == -1 ? 0 : (pp[dir][0][i] - i + n) % n; for (l = 1; l <= LN; l++) for (i = 0; i < n; i++) { int p = pp[dir][l - 1][i]; pp[dir][l][i] = p == -1 ? -1 : pp[dir][l - 1][p]; dd[dir][l][i] = min(dd[dir][l - 1][i] + (p == -1 ? 0 : dd[dir][l - 1][p]), n); } } } int reachable(int i, int j, int dir) { int d_, l, p, d; if (aa[i] > aa[j]) return 0; d_ = dir == 0 ? (j - i + n) % n : (i - j + n) % n; d = 0; for (l = LN; l >= 0; l--) if ((p = pp[dir][l][i]) != -1 && aa[p] <= aa[j]) d = min(d + dd[dir][l][i], n), i = p; return d >= d_; } int compare_plants(int x, int y) { if (reachable(x, y, 0) || reachable(x, y, 1)) return -1; else if (reachable(y, x, 0) || reachable(y, x, 1)) return 1; else 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...