Submission #303201

#TimeUsernameProblemLanguageResultExecution timeMemory
303201tutisComparing Plants (IOI20_plants)C++17
11 / 100
4089 ms219092 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 { set<int>A; inter() {} void add(int i) { A.insert(i); } bool contains(int c) { if (A.count(c)) return true; return false; } }; inter merge(const inter &a, const inter &b) { inter c = a; for (int t : b.A) c.add(t); return c; } struct ST1 { int l, r; inter lazy; 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 fix() { if (l < r) { left->lazy = merge(left->lazy, lazy); right->lazy = merge(right->lazy, lazy); lazy = inter(); } } void add(int x, int y, inter g) { if (x <= l && r <= y) { lazy = merge(lazy, g); return fix(); } fix(); if (y < l || r < x) return; left->add(x, y, g); right->add(x, y, g); } inter get(int x) { if (l == r) return lazy; fix(); if (x <= (l + r) / 2) return left->get(x); else return right->get(x); } } mediss(0, 200000); void adddd(int x, int y, inter c) { while (y >= n) { x -= n; y -= n; } while (x < 0) { x += n; y += n; } if (y < n) { return mediss.add(x, y, c); } else { mediss.add(x, n - 1, c); mediss.add(0, y - n, c); } } inter C[200000]; void init(int k, vector<int> r) { K = k; n = r.size(); N = 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); } 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 = mediss.get(i); c.add(i); C[i] = c; adddd(i - (k - 1), i + (k - 1), c); } } int compare_plants(int x, int y) { if (C[x].contains(y)) return 1; if (C[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...