#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
//#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef uint64_t u64;
typedef int64_t i64;
int k;
struct SegTree {
const ii id = { INT_MAX / 2, -1 };
vii tree;
vi lazySub;
int n, N;
SegTree(vi v) {
n = v.size();
N = 1;
while (N < n)
N *= 2;
tree.resize(2 * N, id);
lazySub.resize(2 * N, 0);
loop(i, n)
tree[N + i] = { v[i], i };
for (int i = N - 1; i >= 1; i--)
tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
}
ii merge(ii a, ii b) {
if (a.first < b.first)
return a;
if (b.first < a.first || b.second - a.second >= k)
return b;
return a;
}
void rangeSub(int l, int r, int v, int i = 1, int tl = 0, int tr = -1) {
if (tr == -1)
tr = N;
if (tl >= r || tr <= l)
return;
if (tl >= l && tr <= r)
{
tree[i].first -= v;
lazySub[i] += v;
return;
}
int tm = (tl + tr) / 2;
rangeSub(l, r, v, i * 2, tl, tm);
rangeSub(l, r, v, i * 2 + 1, tm, tr);
tree[i] = merge(tree[i * 2], tree[i * 2 + 1]);
}
ii range(int l, int r, int i = 1, int tl = 0, int tr = -1) {
if (tr == -1)
tr = N;
if (tl >= r || tr <= l)
return id;
if (i < N)
{
lazySub[2 * i] += lazySub[i];
lazySub[2 * i + 1] += lazySub[i];
tree[2 * i].first -= lazySub[i];
tree[2 * i + 1].first -= lazySub[i];
}
lazySub[i] = 0;
if (tl >= l && tr <= r)
return tree[i];
int tm = (tl + tr) / 2;
return merge(range(l, r, i * 2, tl, tm), range(l, r, i * 2 + 1, tm, tr));
}
void set(int pos, int v, int i = 1, int tl = 0, int tr = -1)
{
if (tr == -1)
tr = N;
if (i < N)
{
lazySub[2 * i] += lazySub[i];
lazySub[2 * i + 1] += lazySub[i];
tree[2 * i].first -= lazySub[i];
tree[2 * i + 1].first -= lazySub[i];
}
lazySub[i] = 0;
if (i >= N)
{
tree[i].first = v;
return;
}
int tm = (tl + tr) / 2;
if (pos < tm)
set(pos, v, i * 2, tl, tm);
else
set(pos, v, i * 2 + 1, tm, tr);
tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
}
};
int n;
vi r;
vi perm;
void init(int _k, vi _r)
{
n = _r.size();
k = _k;
r = _r;
perm.assign(n, 0);
SegTree segTree(r);
int idx = n;
vb vis(n);
/*cout << "R: ";
for (int x : r)
cout << x << ' ';
cout << endl;
cout << "Low: ";*/
while (idx > 0)
{
/*vi lowest;
int count = 0;
for (int i = 1; i < k; i++)
count += vis[i];
loop(i, n)
{
if (r[i] == count && !vis[i])
lowest.push_back(i);
count -= vis[(i + 1) % n];
count += vis[(i + k) % n];
}*/
/*int n2 = lowest.size();
int low = lowest[0];
loop(i, n2 - 1)
{
if (lowest[i + 1] - lowest[i] >= k)
{
low = lowest[i + 1];
break;
}
}*/
auto [lowVal, low] = segTree.range(0, n);
//cout << low << ' ';
if (low - k + 1 < 0)
{
segTree.rangeSub(0, low, 1);
segTree.rangeSub(n + low - k + 1, n, 1);
}
else
{
segTree.rangeSub(low - k + 1, low, 1);
}
segTree.set(low, INT_MAX / 2);
vis[low] = true;
perm[low] = idx--;
}
/*cout << endl;
cout << "Perm: ";
for (int x : perm)
cout << x << ' ';
cout << endl;*/
}
int compare_plants(int x, int y)
{
if (perm[x] < perm[y])
return -1;
if (perm[x] > perm[y])
return 1;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
440 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
440 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
34 ms |
4964 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
