Submission #1065061

#TimeUsernameProblemLanguageResultExecution timeMemory
1065061ZicrusComparing Plants (IOI20_plants)C++17
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> #include "plants.h" using namespace std; typedef long long ll; ll n, pow2, val; vector<ll> seg, laz, a; ll segFind(ll low, ll high, ll nl = 0, ll nh = pow2-1, ll i = 1) { if (i >= pow2) return (seg[i] - laz[i] == 0) ? i-pow2 : -1; if (seg[i] - laz[i] > 0) return -1; laz[2*i] += laz[i]; laz[2*i+1] += laz[i]; seg[i] -= laz[i]; laz[i] = 0; if (low <= nl && high >= nh) { ll v = segFind(low, high, nl, (nl+nh)/2, 2*i); if (v != -1) return v; return segFind(low, high, (nl+nh)/2+1, nh, 2*i+1); } if (low <= (nl+nh)/2) { ll v = segFind(low, high, nl, (nl+nh)/2, 2*i); if (v != -1) return v; } if (high > (nl+nh)/2) { return segFind(low, high, (nl+nh)/2+1, nh, 2*i+1); } return -1; } void segDec(ll low, ll high, ll nl = 0, ll nh = pow2-1, ll i = 1) { if (low <= nl && high >= nh) { laz[i]++; return; } laz[2*i] += laz[i]; laz[2*i+1] += laz[i]; seg[i] -= laz[i]; laz[i] = 0; if (low <= (nl+nh)/2) segDec(low, high, nl, (nl+nh)/2, 2*i); if (high > (nl+nh)/2) segDec(low, high, (nl+nh+1)/2, nh, 2*i+1); seg[i] = min(seg[2*i]-laz[2*i], seg[2*i+1]-laz[2*i+1]); } void segSet(ll i, ll v) { i += pow2; seg[i] = v; i /= 2; while (i > 0) { seg[i] = min(seg[2*i], seg[2*i+1]); i /= 2; } } void init(int k, vector<int> r) { n = val = r.size(); a = vector<ll>(n); pow2 = 1ll << (ll)ceil(log2(2*n)); seg = vector<ll>(2*pow2); laz = vector<ll>(2*pow2); for (int i = 0; i < n; i++) { seg[pow2+i] = r[i]; seg[pow2+n+i] = r[i]; } for (int i = pow2-1; i > 0; i--) { seg[i] = min(seg[2*i], seg[2*i+1]); } while (val > 0) { ll id = segFind(n, 2*n-1); id = segFind(id-k+1, id); id %= n; a[id] = val--; segSet(id, 1ll << 62ll); segSet(id+n, 1ll << 62ll); if (id > 0) segDec(max(0ll, id-k+1), id-1); if (id+2*n-k+1 <= 2*n-1) segDec(id+2*n-k+1, 2*n-1); segDec(id+n-k+1, id+n-1); } return; } int compare_plants(int x, int y) { return a[x] > a[y] ? 1 : -1; } #ifdef TEST #include "grader.cpp" #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...