#include "plants.h"
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define lun(x) (int)x.size()
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<60);
const int inf=(1<<30);
const int nmax=2e5+50;
const ll mod=1e9+7;
using namespace std;
int n,a[nmax],lzy[4*nmax],k;
pair<int,int>st[4*nmax];
pair<int,int> mrg(pair<int,int> x,pair<int,int> y)
{
if(x.fr<y.fr)return x;
else if(y.fr<x.fr)return y;
return mkp(x.fr,min(x.fr,y.fr));
}
void build(int x,int l,int r,vector<int> v)
{
if(l==r)
{
st[x]=mkp(v[l],l);
return;
}
int mid=(l+r)/2;
build(2*x,l,mid,v);
build(2*x+1,mid+1,r,v);
st[x]=mrg(st[2*x],st[2*x+1]);
}
void push(int nod,int l,int r)
{
if(!lzy[nod])return;
st[nod].fr+=lzy[nod];
if(l!=r)
{
lzy[nod*2]+=lzy[nod];
lzy[nod*2+1]+=lzy[nod];
}
lzy[nod]=0;
}
void upd(int nod,int l,int r,int tl,int tr,int v)
{
push(nod,l,r);
if(tl<=l && r<=tr)
{
lzy[nod]+=v;
push(nod,l,r);
return;
}
int mid=(l+r)/2;
if(tl<=mid)upd(nod*2,l,mid,tl,tr,v);
if(mid<tr)upd(nod*2+1,mid+1,r,tl,tr,v);
push(nod*2,l,mid);
push(nod*2+1,mid+1,r);
st[nod]=mrg(st[nod*2],st[nod*2+1]);
}
pair<int,int> qry(int nod,int l,int r,int tl,int tr)
{
if(l>tr || r<tl)return mkp(inf,inf);
push(nod,l,r);
if(tl<=l && r<=tr)return st[nod];
int mid=(l+r)/2;
return mrg(qry(2*nod,l,mid,tl,tr),qry(2*nod+1,mid+1,r,tl,tr));
}
int solve(int x)
{
if(x<k-1)
{
pair<int,int> y=qry(1,0,n-1,x-k+n,n-1);
if(!y.fr)x=y.sc;
}
upd(1,0,n-1,x,x,2*n);
if(x>=k-1)upd(1,0,n-1,x-k+1,x,-1);
else
{
upd(1,0,n-1,0,x,-1);
upd(1,0,n-1,x-k+n,n-1,-1);
}
return x;
}
void init(int K,vector<int> r)
{
k=K;
n=lun(r);
build(1,0,n-1,r);
for(int i=n-1;i>=0;i--)a[solve(qry(1,0,n-1,0,n-1).sc)]=i;
}
int compare_plants(int x,int y)
{
if(a[x]>a[y])return 1;
return -1;
}
/*int main()
{
//freopen("sol.in","r",stdin);
//freopen("sol.out","w",stdout);
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
return 0;
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
