#include <iostream>
#include "plants.h"
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
#define pii pair<int, int>
const int N = 2e5 + 2;
int n;
int k;
vector<int> r;
pii t[4 * N];
int d[4 * N];
vector<int> srt;
int rs[N];
void push(int v, int tl, int tr) {
t[v].first += d[v];
if (tl != tr) {
d[2 * v] += d[v];
d[2 * v + 1] += d[v];
}
d[v] = 0;
}
void build(int v, int tl, int tr) {
//push(v, tl, tr);
if (tl == tr) {
t[v] = pii(r[tl], tl);
return;
}
int tm = (tl + tr) / 2;
build(2 * v, tl, tm);
build(2 * v + 1, tm + 1, tr);
t[v] = min(t[2 * v], t[2 * v + 1]);
}
pii query(int v, int tl, int tr, int l, int r) {
//push(v, tl, tr);
if (tl == l && tr == r) {
return t[v];
}
int tm = (tl + tr) / 2;
if (r <= tm) {
return query(2 * v, tl, tm, l, r);
}
else if (l > tm) {
return query(2 * v + 1, tm + 1, tr, l, r);
}
else {
return min(query(2 * v, tl, tm, l, tm),
query(2 * v + 1, tm + 1, tr, tm + 1, r));
}
}
void update(int v, int tl, int tr, int l, int r, int x) {
push(v, tl, tr);
if (tl == l && tr == r) {
d[v] += x;
push(v, tl, tr);
return;
}
int tm = (tl + tr) / 2;
if (r <= tm) {
update(2 * v, tl, tm, l, r, x);
}
else if (l > tm) {
update(2 * v + 1, tm + 1, tr, l, r, x);
}
else {
update(2 * v, tl, tm, l, tm, x);
update(2 * v + 1, tm + 1, tr, tm + 1, r, x);
}
t[v] = min(t[2 * v], t[2 * v + 1]);
}
void init(int krip, vector<int> rab) {
k = krip;
r.push_back(-1);
for (int x : rab)
r.push_back(x);
n = r.size() - 1;
build(1, 1, n);
//cout << t[1].first << " " << t[1].second << endl;
for (int i = 0; i < n; i++) {
pii cur = query(1, 1, n, 1, n);
int mn = cur.first, mni = cur.second;
if (mni + k <= n) {
cur = query(1, 1, n, mni + k, n);
if (cur.first == mn) {
mn = cur.first;
mni = cur.second;
}
}
if (mni - k + 1 >= 1) {
update(1, 1, n, mni - k + 1, mni - 1, -1);
}
else {
if(mni != 1)
update(1, 1, n, 1, mni - 1, -1);
update(1, 1, n, n - (mni - k) + 1, n, -1);
}
update(1, 1, n, mni, mni, N);
}
reverse(srt.begin(), srt.end());
for (int i = 0; i < srt.size(); i++) {
rs[srt[i]] = i;
}
return;
}
int compare_plants(int x, int y) {
x++;
y++;
if (rs[x] < rs[y])
return -1;
else
return 1;
}
/*
4 3 2
0 1 1 2
0 2
1 2
*/
Compilation message
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:108:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for (int i = 0; i < srt.size(); i++) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
