#include<bits/stdc++.h>
using namespace std;
#include "plants.h"
const int N = 2e5 + 10;
int p[N], T[N << 2], lazy[N << 2];
void push(int s, int l, int r) {
if (!lazy[s]) return;
T[s] += lazy[s];
if (l != r) {
lazy[s << 1] += lazy[s];
lazy[s << 1 | 1] += lazy[s];
}
lazy[s] = 0;
}
void up(int s, int l, int r, int from, int to, int val) {
if (l > to || r < from) return;
if (from <= l && r <= to) {
lazy[s] = val;
push(s, l, r);
return;
}
int mid = l + r >> 1;
up(s << 1, l, mid, from, to, val);
up(s << 1 | 1, mid + 1, r, from, to, val);
T[s] = min(T[s << 1], T[s << 1 | 1]);
}
int get(int s, int l, int r, int from, int to) {
push(s, l, r);
if (l > to || r < from || T[s]) return -1;
if (l == r) return l;
int mid = l + r >> 1;
int ret = get(s << 1 | 1, mid + 1, r, from, to);
if (ret >= 0) return ret;
return get(s << 1, l, mid, from, to);
}
void init(int k, std::vector<int> r) {
int n = r.size();
for(int i = 0; i < n; i++) up(1, 0, n - 1, i, i, r[i]);
int val = n - 1;
auto dfs = [&] (auto self, int i) -> void {
// cerr << i << endl;
while (1) {
int left = get(1, 0, n - 1, max(0, i - k + 1), i - 1);
if (left >= 0) self(self, left);
else if (i - k + 1 < 0) {
left = get(1, 0, n - 1, n + i - k + 1, n - 1);
if (left >= 0) self(self, left);
else break;
}
else break;
}
p[i] = val--;
up(1, 0, n - 1, i, i, 1e9);
up(1, 0, n - 1, max(0, i - k + 1), i - 1, -1);
if (i - k + 1 < 0) up(1, 0, n - 1, n + i - k + 1, n - 1, -1);
};
while (1) {
int pos = get(1, 0, n - 1, 0, n - 1);
if (pos < 0) break;
dfs(dfs, pos);
}
for(int i = 0; i < n; i++) cout << p[i] << " "; cout << endl;
}
int compare_plants(int x, int y) {
if (p[x] < p[y]) return -1;
return 1;
}
#ifdef ngu
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 ("task.inp", "r", stdin);
freopen ("task.out", "w", stdout);
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;
}
#endif // ngu
Compilation message
plants.cpp: In function 'void up(int, int, int, int, int, int)':
plants.cpp:26:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
26 | int mid = l + r >> 1;
| ~~^~~
plants.cpp: In function 'int get(int, int, int, int, int)':
plants.cpp:36:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
36 | int mid = l + r >> 1;
| ~~^~~
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:73:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
73 | for(int i = 0; i < n; i++) cout << p[i] << " "; cout << endl;
| ^~~
plants.cpp:73:51: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
73 | for(int i = 0; i < n; i++) cout << p[i] << " "; cout << endl;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
