萌新刚学1sOI,求助
查看原帖
萌新刚学1sOI,求助
238729
The_Out_Land楼主2020/10/23 17:36

为什么它会OLEOLE啊?

我在LOJLOJ上可以跑过去诶

/*************************************************************************
	> File Name: P6619.cpp
	> Author: The-Out-Land
	> Mail: 2264454706@qq.com 
	> Created Time: 2020年10月23日 星期五 08时11分48秒
 ************************************************************************/

#include <bits/stdc++.h>

#define enter putchar('\n')
#define space putchar(' ')
#define re register
#define N 6010000
#define int long long

using namespace std;

inline int max(int x,int y){return (x>y?x:y);}

inline int min(int x,int y){return (x<y?x:y);}

inline int read(){
	int x=0;char c=getchar();bool y=1;
	for(;c<'0' || c>'9';c=getchar()) if(c=='-') y=0;
	for(;c>='0' && c<='9';c=getchar()) x=(x<<1)+(x<<3)+c-48;
	if(y) return x;
	return -x;
}

int st[50],top;

inline void write(int x){
	while(x) st[++top]=x%10,x/=10;
	if(!top) return putchar('0'),void();
	while(top) putchar('0'+st[top--]);
	return;
}

int q,b[N],A,B,C,S[2],n;

int s[N][2];

struct data{
	int opt,fi,se,th;
	data(const int X=0,const int Y=0,const int Z=0,const int W=0):opt(X),fi(Y),se(Z),th(W){}
}a[N];

inline int lower(int x){
	int l=1,r=n,mid;
	while(l<r){
		mid=(l+r)>>1;
		if(b[mid]<x)	l=mid+1;
		else			r=mid;
	}
	return l;
}

struct Segment_Tree{
	#define ls (x<<1)
	#define rs (x<<1|1)
	int T[N<<2][2],R1,R2;
	inline void pushup(int x){
		T[x][0]=T[ls][0]+T[rs][0];
		T[x][1]=T[ls][1]+T[rs][1];
		return;
	}
	void modify(int x,int l,int r,int y,int val,int opt){
		if(l==r){T[x][opt]+=val;return;}
		int mid=(l+r)>>1;
		if(y<=mid)	modify(ls,l,mid,y,val,opt);
		else		modify(rs,mid+1,r,y,val,opt);
		pushup(x);
		return;
	}
	void query(int x,int l,int r){
		if(l==r){A+=T[x][0],B+=T[x][1];C=l;return;}
		int mid=(l+r)>>1,opt=1;
		A+=T[ls][0],B+=T[rs][1];
		if(A+s[mid+1][0]>=B) opt=0;
		if(opt==0)	return A-=T[ls][0],query(ls,l,mid);
		else		return B-=T[rs][1],query(rs,mid+1,r);
	}

	void find(int x,int l,int r){
		if(l==r){A+=T[x][1];C=l;return;}
		int mid=(l+r)>>1;
		if(A+T[rs][1]>=B)	return find(rs,mid+1,r);
		else				return A+=T[rs][1],find(ls,l,mid);
	}
}tree;

int ans,r1,r2;

inline void Input(){
	q=read();
	for(re int i=1;i<=q;++i){
		a[i].opt=read();
		if(a[i].opt==1){
			a[i].fi=read(),a[i].se=read(),a[i].th=read();
			b[++n]=a[i].se;
		}
		else{
			a[i].fi=read();
		}
	}
	sort(b+1,b+n+1);
	n=unique(b+1,b+n+1)-b-1;
	for(re int i=1;i<=q;++i) if(a[i].opt==1) a[i].se=lower(a[i].se);
	return;
}

inline void solve(){
	for(re int i=1;i<=q;++i){
		if(a[i].opt==1){
			tree.modify(1,1,n,a[i].se,a[i].th,a[i].fi);
			s[a[i].se][a[i].fi]+=a[i].th;
			S[a[i].fi]+=a[i].th;
		}
		else{
			int id=a[i].fi;
			tree.modify(1,1,n,a[id].se,-a[id].th,a[id].fi);
			s[a[id].se][a[id].fi]-=a[id].th;
			S[a[id].fi]-=a[id].th;
		}
		if(!S[0] || !S[1]) {puts("Peace");continue;}
		A=0,B=0;C=0;
		tree.query(1,1,n);
		r1=C;ans=min(A,B);
		//assert(A<B);
		B-=s[C][1];
		++C;
		A+=s[C][0];
		if(min(A,B)>=ans)
		{
			ans=B,A=0,tree.find(1,1,n),r1=C;
		}
		if(!ans) puts("Peace");
		else
		printf("%lld %lld\n",b[r1],(ans<<1));
		//write(b[r1]),space,write(ans<<1),enter;
	}
	return;
}

signed main(){
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
	Input();
	solve();
	return 0;
}
2020/10/23 17:36
加载中...