제출 #790622

#제출 시각아이디문제언어결과실행 시간메모리
790622resting식물 비교 (IOI20_plants)C++17
44 / 100
1157 ms122408 KiB
#include "plants.h" #include <bits/stdc++.h> using namespace std; #define time fuck const int mx = 2e5 + 5; int n, k; struct segtree { int l, r, lz = 0, mn = 0; segtree* lc = 0, * rc = 0; segtree* getmem(); segtree() : segtree(-1, -1) {}; segtree(int l, int r) : l(l), r(r) { if (l == r)return; int m = (l + r) / 2; lc = getmem(); *lc = segtree(l, m); rc = getmem(); *rc = segtree(m + 1, r); } void apply(int v) { mn += v; lz += v; } void push() { if (l == r) return; lc->apply(lz);rc->apply(lz); lz = 0; } void pull() { if (l == r) return; mn = min(lc->mn, rc->mn); } void upd(int ql, int qr, int qv) { if (qr < 0) { ql += n; qr += n; } if (ql < 0) { upd(0, qr, qv); upd((n)+ql, (n - 1), qv); return; } if (ql >= n) { ql -= n; qr -= n; } if (qr >= n) { upd(ql, (n - 1), qv); upd(0, qr - (n), qv); return; } if (l > qr || r < ql) return; if (ql <= l && r <= qr) { apply(qv); return; } push(); lc->upd(ql, qr, qv); rc->upd(ql, qr, qv); pull(); } int extract_min() { if (l == r) return l; push(); if (lc->mn == mn) return lc->extract_min(); return rc->extract_min(); } }mem[mx * 8]; int memsz = 0; segtree* segtree::getmem() { return &mem[memsz++]; } const int inf = 1e9 + 7; namespace rmq { struct segtree { int l, r, lz = 0; segtree* lc = 0, * rc = 0; pair<int, int> v = { 0, -1 }; segtree* getmem(); segtree() : segtree(-1, -1) {}; segtree(int l, int r) : l(l), r(r) { if (l == r)return; int m = (l + r) / 2; lc = getmem(); *lc = segtree(l, m); rc = getmem(); *rc = segtree(m + 1, r); } void upd(int qi, int qv) { if (l == r) { v = { qv, qi };return; } if (qi <= lc->r) lc->upd(qi, qv); else rc->upd(qi, qv); v = min(lc->v, rc->v); } pair<int, int> q(int ql, int qr) { if (qr < 0) { ql += n; qr += n; } if (ql < 0) { return min(q(0, qr), q((n)+ql, (n - 1))); } if (ql >= n) { ql -= n; qr -= n; } if (qr >= n) { return min(q(ql, (n - 1)), q(0, qr - (n))); } if (l > qr || r < ql)return { 0, -1 }; if (ql <= l && r <= qr) return v; return min(lc->q(ql, qr), rc->q(ql, qr)); } }mem[mx * 4]; int memsz = 0; segtree* segtree::getmem() { return &mem[memsz++]; } } vector<int> time, rtime; int parl[mx][20], parr[mx][20]; void init(int kk, std::vector<int> r) { n = r.size();k = kk;k--; time = rtime = vector<int>(n, 0); segtree parta(0, n - 1), partb(0, n - 1); partb.upd(0, n - 1, 1); for (int i = 0; i < n; i++) parta.upd(i, i, r[i]); for (int i = 0; i < n; i++) { while (parta.mn == 0) { int t = parta.extract_min(); parta.upd(t, t, mx); partb.upd(t, t, -1); partb.upd(t + 1, t + k, 1); } int t = partb.extract_min(); time[t] = i; rtime[i] = t; partb.upd(t, t, mx); partb.upd(t + 1, t + k, -1); parta.upd(t - k, t, -1); } rmq::segtree tim(0, n - 1); for (int i = 0; i < n; i++) { int t = tim.q(rtime[i] - k, rtime[i]).second; if (t == -1) parl[rtime[i]][0] = rtime[i]; else parl[rtime[i]][0] = t; t = tim.q(rtime[i], rtime[i] + k).second; if (t == -1) parr[rtime[i]][0] = rtime[i]; else parr[rtime[i]][0] = t; } for (int i = 1; i < 20; i++) { for (int j = 0; j < n; j++) { if (parl[j][0] > j) parl[j][i] = parl[j][i - 1]; else if (parl[parl[j][i - 1]][i - 1] > j) parl[j][i] = parl[j][i - 1]; else parl[j][i] = parl[parl[j][i - 1]][i - 1]; } } for (int i = 1; i < 20; i++) { for (int j = 0; j < n; j++) { if (parr[j][0] < j) parr[j][i] = parr[j][i - 1]; else if (parr[parr[j][i - 1]][i - 1] < j) parr[j][i] = parr[j][i - 1]; else parr[j][i] = parr[parr[j][i - 1]][i - 1]; } } return; } int compare_plants(int x, int y) { //compare zero if (x + k >= y || y + k - n >= x) { return time[x] < time[y] ? 1 : -1; } //compare one int t = x; for (int i = 19; i >= 0; i--) { if (parr[t][i] + k < y) t = parr[t][i]; } t = parr[t][0]; if (t + k >= y && time[t] > time[y]) return -1; //compare two t = parl[x][19]; if (y + k - n >= t && time[y] < time[t]) return -1; t = parl[t][0]; for (int i = 19; i >= 0; i--) { if (y + k < parl[t][i]) t = parl[t][i]; } t = parl[t][0]; if (y + k >= t && time[y] < time[t])return -1; //compare three t = y; for (int i = 19; i >= 0; i--) { if (x + k < parl[t][i]) t = parl[t][i]; } t = parl[t][0]; if (x + k >= t && time[t] > time[x]) return 1; //compare four t = parr[y][19]; if (t + k - n >= x && time[t] > time[x]) return 1; t = parr[t][0]; for (int i = 19; i >= 0; i--) { if (parr[t][i] + k < x) t = parr[t][i]; } t = parr[t][0]; if (t + k >= x && time[t] > time[x]) return 1; return 0; } // int main() { // init(3, { 0, 1, 1, 2 }); // cout << compare_plants(0, 2) << endl; // cout << compare_plants(1, 2) << endl; // }
#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...