#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
int K;
int n;
vector<int> b;
int INF = 1LL<<30;
int tree[524288];
int lazy[524288]; //min add segtree
void push(int v, int tl, int tr) {
if (tl<tr) {
lazy[2*v]+=lazy[v];
lazy[2*v+1]+=lazy[v];
}
tree[v]+=lazy[v];
lazy[v] = 0;
}
void update(int v, int l, int r, int tl, int tr, int addend) {
push(v,tl,tr);
if (l>tr || r<tl) return;
if (l<=tl && tr<=r) {
if (tl<tr) {
lazy[2*v]+=addend;
lazy[2*v+1]+=addend;
}
tree[v]+=addend;
return;
}
int m = (tl+tr)/2;
update(2*v,l,r,tl,m,addend);
update(2*v+1,l,r,m+1,tr,addend);
tree[v] = min(tree[2*v],tree[2*v+1]);
}
int query(int v, int l, int r, int tl, int tr) {
push(v,tl,tr);
if (l>tr || r<tl) return INF;
if (l<=tl && tr<=r) return tree[v];
int m = (tl+tr)/2;
return min(query(2*v,l,r,tl,m),query(2*v+1,l,r,m+1,tr));
}
int query2(int v, int l, int r, int tl, int tr) {
//finds the first 0 in range (l,r)
push(v,tl,tr);
for (int i=l; i<=r; i++) {
update(1,i,i,0,262143,0); //to push
if (tree[262144+i]==0) {
return i;
}
}
return INF;
if (tree[v]!=0) {
return INF;
}
}
vector<int> p;
void init(int k, std::vector<int> r) {
for (int i=0; i<524288; i++) tree[i] = lazy[i] = INF;
K=k;
b=r;
n=r.size();
p=vector<int>(n,-1);
for (int i=0; i<n; i++) {
update(1,i,i,0,262143,r[i]);
}
//let l[i] be the number of plants j in the k-1 indices before i such that i is higher than j
//any 0 value is higher than the k-1 indices after it
//get any 0 that does not have a 0 in the k-1 indices before
//and subtract 1 from these indices
int height = n;
for (int op=0; op<n; op++) {
/*cout << "SEGTREE STATE" << endl;
for (int i=0; i<n; i++) {
cout << query(1,i,i,0,262143) <<" ";
}
cout << endl;*/
int x = query2(1,0,n-1,0,262143);
assert(x!=INF);
int li = x-k+1; li%=n; li+=n; li%=n;
int ri = x-1; ri%=n; ri+=n; ri%=n;
int an = INF;
int jambloat = -1;
if (li<=ri) {
an=min(query(1,li,ri,0,262143),INF);
}
else {
an=min(query(1,li,n-1,0,262143),query(1,0,ri,0,262143));
}
if (an!=0) {
jambloat = x;
}
else {
if (li<=ri) {
jambloat=min(query2(1,li,ri,0,262143),INF);
}
else {
if (query2(1,li,n-1,0,262143)>=INF/2) {
jambloat = query2(1,0,ri,0,262143);
}
else {
jambloat=query2(1,li,n-1,0,262143);
}
}
}
li = jambloat-k+1; li%=n; li+=n; li%=n;
ri = jambloat-1; ri%=n; ri+=n; ri%=n;
if (li<=ri) {
update(1,li,ri,0,262143,-1);
}
else {
update(1,li,n-1,0,262143,-1);
update(1,0,ri,0,262143,-1);
}
update(1,jambloat,jambloat,0,262143,INF-query(1,jambloat,jambloat,0,262143));
//cout << "doing " << jambloat << endl;
p[jambloat] = height;
height--;
}
/*for (int i=0; i<n; i++) {
cout << p[i] <<" ";
}
cout << endl;*/
return;
}
int compare_plants(int x, int y) {
if (p[x]<p[y]) return 1;
else if (p[x]>p[y]) return -1;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
