IOI交互编译失败
查看原帖
IOI交互编译失败
225192
Raymondzll楼主2023/11/17 13:08

请问到底该如何实现?

#include <bits/stdc++.h>
using namespace std;
int n,k;
int val[1600010],tag[1600010];
void pushdown(int id){
	val[id<<1]+=tag[id];val[id<<1|1]+=tag[id];
	tag[id<<1]+=tag[id];tag[id<<1|1]+=tag[id];
	tag[id]=0;
}
void update(int id,int l,int r,int ql,int qr,int delta){
	if(r<ql||l>qr)return;
	if(l>=ql&&r<=qr){val[id]+=delta;tag[id]+=delta;return;}
	pushdown(id);
	int mid=(l+r)>>1;
	update(id<<1,l,mid,ql,qr,delta);
	update(id<<1|1,mid+1,r,ql,qr,delta);
	val[id]=min(val[id<<1],val[id<<1|1]);
}
int query(int id,int l,int r){
	if(val[id]>0)return -1;
	if(l==r)return l;
	pushdown(id);
	int mid=(l+r)>>1;
	if(val[id<<1]>0)return query(id<<1|1,mid+1,r);
	return query(id<<1,l,mid);
}
void upd(int ql,int qr,int delta){
	ql++;qr++;update(1,1,2*n,ql,qr,delta);
}
int que(){
	return query(1,1,2*n)-1;
}
int stk[400010],top;
vector<int> solve(vector<int>r){
	vector<int>ans(r.size());
	top=0;memset(val,0,sizeof(val));memset(tag,0,sizeof(tag));
	for(int i=0;i<2*n;i++)upd(i,i,r[i]);
	for(int i=1;i<=2*n;i++){
		int x=que();
		while(x<0&&top){
			upd(stk[top],2*n-1,-1);
			top--;x=que();
		}
		ans[x]=i;
		upd(x,x,0x3f3f3f3f);
		upd(x-k+1,x-1,-1);
		if(x-k+1<0)stk[++top]=2*n+x-k;
	}
	return ans;
}
vector<int>v1,v2;
void init(int K,vector<int>R){
	n=R.size();k=K;
	for(int i=0;i<n;i++)R.push_back(R[i]);
	v1=solve(R);
	for(int i=0;i<2*n;i++)R[i]=k-R[i]-1;
	v2=solve(R);
}
int compare_plants(int x,int y){
	if(x>y)return -compare_plants(y,x);
	if(v1[x]>v1[y]||v2[x+n]<v2[y])return -1;
	if(v2[x]>v2[y]||v1[x+n]<v1[y])return 1;
	return 0;
}
2023/11/17 13:08
加载中...