This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
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 (seg[2*i]-laz[2*i] == 0) 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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |