제출 #303185

#제출 시각아이디문제언어결과실행 시간메모리
303185tutis식물 비교 (IOI20_plants)C++17
32 / 100
2040 ms2097156 KiB
#include "plants.h" #include <bits/stdc++.h> using namespace std; vector<int>k0, k1; int K, n; vector<int>A; struct ST { int l, r; pair<int, int> mn; pair<int, int> mn1; int del = 0; int del1 = 0; ST *left, *right; ST(int l, int r, vector<int>&a): l(l), r(r) { if (l < r) { left = new ST(l, (l + r) / 2, a); right = new ST((l + r) / 2 + 1, r, a); mn = min(left->mn, right->mn); } else mn = {a[l], l}; mn1 = mn; } void fix() { if (l == r) { mn.first += del; del = 0; } else { mn.first += del; left->del += del; right->del += del; del = 0; } } void fix1() { if (l == r) { mn1.first += del1; del1 = 0; } else { mn1.first += del1; left->del1 += del1; right->del1 += del1; del1 = 0; } } void add(int x, int y, int w) { if (x <= l && r <= y) { del += w; return fix(); } fix(); if (r < x || y < l) return; left->add(x, y, w); right->add(x, y, w); mn = min(left->mn, right->mn); } void add1(int x, int y, int w) { if (x <= l && r <= y) { del1 += w; return fix1(); } fix1(); if (r < x || y < l) return; left->add1(x, y, w); right->add1(x, y, w); mn1 = min(left->mn1, right->mn1); } }; int id[200000]; int N; struct inter { vector<pair<int, int>>A; inter() {} void add(int i) { A.push_back({i, i}); } bool contains(int c) { for (auto i : A) if (i.first <= c && c <= i.second) return true; return false; } }; inter merge(inter a, inter b) { for (pair<int, int>g : b.A) a.A.push_back(g); return a; } struct ST1 { int l, r; inter xx; ST1 *left, *right; ST1(int l, int r): l(l), r(r) { if (l < r) { left = new ST1(l, (l + r) / 2); right = new ST1((l + r) / 2 + 1, r); } } void set(int i, inter g) { if (l == r) { xx = g; } else { if (i <= (l + r) / 2) left->set(i, g); else right->set(i, g); xx = merge(left->xx, right->xx); } } inter get(int x, int y) { if (x <= l && r <= y) return xx; if (y < l || r < x) return inter(); return merge(left->get(x, y), right->get(x, y)); } } mediss(0, 200000); inter gett(int x, int y) { while (y >= n) { x -= n; y -= n; } while (x < 0) { x += n; y += n; } if (y < n) { return mediss.get(x, y); } else { return merge(mediss.get(x, n - 1), mediss.get(0, y - n)); } } void init(int k, vector<int> r) { K = k; n = r.size(); N = n; if (k == 2) { k0 = k1 = vector<int>(n, 0); for (int t = 0; t < 2; t++) for (int i = n - 1; i >= 0; i--) { if (r[i] == 0) k0[i] = 1 + k0[(i + 1) % n]; else k1[i] = 1 + k1[(i + 1) % n]; } return; } if (2 * k > n) { ST medis(0, n - 1, r); auto add = [&](int x, int y, int w) { while (y >= n) { x -= n; y -= n; } while (x < 0) { x += n; y += n; } if (y < n) { medis.add(x, y, w); } else { medis.add(x, n - 1, w); medis.add(0, y - n, w); } }; auto add1 = [&](int x, int y, int w) { while (y >= n) { x -= n; y -= n; } while (x < 0) { x += n; y += n; } if (y < n) { medis.add1(x, y, w); } else { medis.add1(x, n - 1, w); medis.add1(0, y - n, w); } }; while (medis.mn1.first == 0) { int i = medis.mn1.second; add(i + 1, i + (k - 1), 1); add1(i, i, 1); } A = vector<int>(n, -1); for (int tt = 0; tt < n; tt++) { while (medis.mn1.first == 0) { int i = medis.mn1.second; add(i + 1, i + (k - 1), 1); add1(i, i, 1); } int i = medis.mn.second; add(i + 1, i + (k - 1), -1); add(i - (k - 1), i - 1, -1); add1(i - (k - 1), i - 1, -1); A[i] = tt; add(i, i, n + 10000); add1(i, i, n + 10000); r[i] = n + 100; } return; } ST medis(0, n - 1, r); auto add = [&](int x, int y, int w) { while (y >= n) { x -= n; y -= n; } while (x < 0) { x += n; y += n; } if (y < n) { medis.add(x, y, w); } else { medis.add(x, n - 1, w); medis.add(0, y - n, w); } }; auto add1 = [&](int x, int y, int w) { while (y >= n) { x -= n; y -= n; } while (x < 0) { x += n; y += n; } if (y < n) { medis.add1(x, y, w); } else { medis.add1(x, n - 1, w); medis.add1(0, y - n, w); } }; while (medis.mn1.first == 0) { int i = medis.mn1.second; add(i + 1, i + (k - 1), 1); add1(i, i, 1); } vector<int>K; for (int tt = 0; tt < n; tt++) { while (medis.mn1.first == 0) { int i = medis.mn1.second; add(i + 1, i + (k - 1), 1); add1(i, i, 1); } int i = medis.mn.second; add(i + 1, i + (k - 1), -1); add(i - (k - 1), i - 1, -1); add1(i - (k - 1), i - 1, -1); add(i, i, n + 10000); add1(i, i, n + 10000); id[i] = tt; K.push_back(i); r[i] = n + 100; } reverse(K.begin(), K.end()); vector<int>ok; for (int i : K) { inter c = gett(i - (k - 1), i + (k - 1)); c.add(i); mediss.set(i, c); } } int compare_plants(int x, int y) { assert(x < y); if (K == 2) { if (k0[x] >= y - x) return 1; if (k1[x] >= y - x) return -1; if (k0[y] >= n - y + x) return -1; if (k1[y] >= n - y + x) return 1; return 0; } if (!A.empty()) { if (A[x] < A[y]) return 1; else return -1; } if (mediss.get(x, x).contains(y)) return 1; if (mediss.get(y, y).contains(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...