Submission #418915

#TimeUsernameProblemLanguageResultExecution timeMemory
418915usachevd0Comparing Plants (IOI20_plants)C++17
14 / 100
4050 ms5212 KiB
#include <bits/stdc++.h> #ifndef LOCAL #include "plants.h" #endif using namespace std; #define fi first #define se second #define mp make_pair #define pb push_back #define all(a) (a).begin(), (a).end() #define Time (clock() * 1.0 / CLOCKS_PER_SEC) using ll = long long; using ull = unsigned long long; using pii = pair<int, int>; using pil = pair<int, ll>; using pli = pair<ll, int>; using pll = pair<ll, ll>; using ld = long double; template<typename T1, typename T2> bool chkmin(T1& x, T2 y) { return y < x ? (x = y, true) : false; } template<typename T1, typename T2> bool chkmax(T1& x, T2 y) { return y > x ? (x = y, true) : false; } void debug_out() { cerr << endl; } template<typename T1, typename... T2> void debug_out(T1 A, T2... B) { cerr << ' ' << A; debug_out(B...); } template<typename T> void mdebug_out(T* a, int n) { for (int i = 0; i < n; ++i) cerr << a[i] << ' '; cerr << endl; } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n) #else #define debug(...) 1337 #define mdebug(a, n) 1337 #endif template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) { for (auto& e : v) stream << e << ' '; return stream; } template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) { return stream << p.first << ' ' << p.second; } namespace sol { const int INF32 = 1e9; const int maxN = 2e5 + 5; int n, k; int r[maxN]; int rem[maxN]; int f[maxN]; int prior[maxN]; int md(int i) { return (i % n + n) % n; } bool in_seg(int x, int l, int r) { if (l <= r) return l <= x && x <= r; return x >= l || x <= r; } namespace sgt { const int logN = 18; const int N = 1 << logN; int mn[2 * N]; int lazy[2 * N]; void apply(int v, int delta) { mn[v] += delta; lazy[v] += delta; } void push(int v) { if (!lazy[v]) return; apply(v << 1, lazy[v]); apply(v << 1 | 1, lazy[v]); lazy[v] = 0; } void upd(int v) { mn[v] = min(mn[v << 1], mn[v << 1 | 1]); } void build(int v, int vl, int vr) { if (vl == vr) { mn[v] = rem[v]; return; } int vm = (vl + vr) >> 1; build(v << 1, vl, vm); build(v << 1 | 1, vm + 1, vr); upd(v); } void add(int v, int vl, int vr, int l, int r, int delta) { if (l > r || vr < l || r < vl || !delta) return; if (l <= vl && vr <= r) { apply(v, delta); return; } int vm = (vl + vr) >> 1; push(v); add(v << 1, vl, vm, l, r, delta); add(v << 1 | 1, vm + 1, vr, l, r, delta); upd(v); } void disable(int v, int vl, int vr, int i) { if (vl == vr) { mn[v] = +INF32; return; } int vm = (vl + vr) >> 1; push(v); if (i <= vm) disable(v << 1, vl, vm, i); else disable(v << 1 | 1, vm + 1, vr, i); upd(v); } int getFirstZero(int v, int vl, int vr) { if (mn[v] > 0) return -1; if (vl == vr) return vl; int vm = (vl + vr) >> 1; push(v); if (mn[v << 1] == 0) return getFirstZero(v << 1, vl, vm); return getFirstZero(v << 1 | 1, vm + 1, vr); } } } void init(int _k, vector<int> _r) { using namespace sol; n = _r.size(); k = _k; for (int i = 0; i < n; ++i) r[i] = _r[i]; for (int i = 0; i < n; ++i) f[i] = r[i]; for (int i = 0; i < n; ++i) if (r[i] == 0) for (int j = 1; j < k; ++j) ++f[md(i + j)]; // sgt::build(1, 0, n - 1); for (int y = 0; y < n; ++y) { // mdebug(f, n); assert(count(f, f + n, 0) == 1); int i = find(f, f + n, 0) - f; // debug(i); prior[i] = y; f[i] = +INF32; for (int j = 1; j < k; ++j) { --f[md(i + j)]; } for (int j = 1; j < k; ++j) { int t = md(i - j); --f[t]; if (--r[t] == 0) { for (int j = 1; j < k; ++j) ++f[md(t + j)]; } } } } int compare_plants(int x, int y) { using namespace sol; if (prior[x] < prior[y]) return 1; return -1; } #ifdef LOCAL static int n, k, q; static std::vector<int> r; static std:: vector<int> x; static std:: vector<int> y; static std:: vector<int> answer; int main() { freopen("in", "r", stdin); assert(scanf("%d%d%d", &n, &k, &q) == 3); r.resize(n); answer.resize(q); for (int i = 0; i < n; i++) { int value; assert(scanf("%d", &value) == 1); r[i] = value; } x.resize(q); y.resize(q); for (int i = 0; i < q; i++) { assert(scanf("%d%d", &x[i], &y[i]) == 2); } fclose(stdin); init(k, r); for (int i = 0; i < q; i++) { answer[i] = compare_plants(x[i], y[i]); } for (int i = 0; i < q; i++) { printf("%d\n", answer[i]); } fclose(stdout); return 0; } // int32_t main() { // #ifdef LOCAL // freopen("in", "r", stdin); // #endif // ios::sync_with_stdio(0); // cin.tie(0); // return 0; // } #endif
#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...