Submission #303163

#TimeUsernameProblemLanguageResultExecution timeMemory
303163tutisComparing Plants (IOI20_plants)C++17
32 / 100
1646 ms49032 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 { int a, b; inter() {} inter(int x, int y) { a = x; b = y; } bool contains(int c) { if (a == -1 || b == -1) return false; if (a <= c && c <= b) return true; if (a > b) if (c >= a || c <= b) return true; return false; } }; inter merge(inter a, inter b) { if (a.a == -1) return b; if (b.a == -1) return a; if (a.a <= a.b && b.a <= b.b) { if (a.a == 0 && b.b == n - 1) { if (b.a > a.b) return inter(b.a, a.b); else return inter(1, 0); } return inter({min(a.a, b.a), max(a.b, b.b)}); } if (a.a < a.b && b.a < b.b) { int x = min(a.a, b.a); int y = max(a.b, b.b); if (x <= y) return inter(1, 0); return inter(x, y); } if (a.a < a.b) { if (b.contains(a.a) || b.contains(a.a - 1)) { int x = min(a.a, b.a); if (x <= a.b) return inter(1, 0); return inter(x, a.b); } else { int y = max(a.b, b.b); if (a.a <= y) return inter(1, 0); return inter(a.a, y); } } } 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); } xx = inter(l, 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(-1, -1); 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) { mediss.set(i, gett(i - (k - 1), i + (k - 1))); } } 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 (id[x] > id[y]) return -compare_plants(y, x); if (mediss.get(x, x).contains(y)) return -1; return 0; }

Compilation message (stderr)

plants.cpp: In function 'inter merge(inter, inter)':
plants.cpp:150:1: warning: control reaches end of non-void function [-Wreturn-type]
  150 | }
      | ^
#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...