QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#721769#8338. Quad Kingdoms ChessAnotherDayofSun#RE 0ms0kbC++142.5kb2024-11-07 16:47:382024-11-07 16:47:39

Judging History

你现在查看的是最新测评结果

  • [2024-11-07 16:47:39]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-11-07 16:47:38]
  • 提交

answer

#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);i++) 
#define re
#define vi vector<int>
#define pb push_back
#define ll long long
#define P 998244353
using namespace std;
inline int read(){
	re char c;int res=0;bool flag=0;
	while(c=getchar(),c<48)(c=='-')&&(flag=1);
	do res=(res<<3)+(res<<1)+(c^48);
	while(c=getchar(),c>47);
	flag&&(res=-res);
	return res; 
}
const int MN=1e5+5; 
int n,a[MN]; 
struct ds {
	static const int N=MN<<2; 
	#define ls (k<<1)
	#define rs (k<<1|1)
	#define mid ((l+r)>>1)
	int mx[N],cnt[N];
	ll sum[N],ans[N]; 
	void qry2(int k,int l,int r,int &tcnt,ll &tsum,ll &tans,int nowmx) {
		if(l==r) {
			if(mx[k]>=nowmx) tcnt=cnt[k],tsum=sum[k],tans=ans[k];
			else tcnt=0,tsum=0,tans=0;
			return; 
		}
		if(mx[rs]>=nowmx) {
			qry2(rs,mid+1,r,tcnt,tsum,tans,nowmx); 
			int lcnt=cnt[k]-cnt[rs]; 
			int lsum=sum[k]-sum[rs];
			int lans=(ans[k]-ans[rs])-lsum*cnt[rs];
			tcnt+=lcnt,tsum+=lsum,tans+=lans;
		} else qry2(ls,l,mid,tcnt,tsum,tans,nowmx); 
	}
	void pushup(int k,int l,int r) {
		mx[k]=max(mx[ls],mx[rs]);
		if(mx[rs]>mx[ls]) cnt[k]=cnt[rs],sum[k]=sum[rs],ans[k]=ans[rs]; 
		else {
			int tcnt; ll tsum,tans; 
			qry2(ls,l,mid,tcnt,tsum,tans,mx[rs]);
			cnt[k]=tcnt+cnt[rs],sum[k]=tsum+sum[rs],ans[k]=tans+tsum*cnt[rs]+ans[rs];
		}
	}
	void upd(int k,int l,int r,int p,int v) {
		if(l==r) {
			mx[k]=sum[k]=ans[k]=v; 
			cnt[k]=1; 
			return; 
		}
		if(p<=mid) upd(ls,l,mid,p,v); 
		else upd(rs,mid+1,r,p,v); 
		pushup(k,l,r); 
	}
	void build(int k,int l,int r,int *a) {
		if(l==r) {
			mx[k]=sum[k]=ans[k]=a[l]; 
			cnt[k]=1; 
			return; 
		}
		build(ls,l,mid,a),build(rs,mid+1,r,a); 
		pushup(k,l,r); 
	}
	pair<ll,int> qry() {
		return make_pair(ans[1],cnt[1]); 
	}
	#undef mid
}; 
struct tpw {
	static const int N=4e5+5; 
	int n,a[N];  ds t;
	void rd() {
		n=read();
		For(i,1,n) a[i]=read();
		t.build(1,1,n,a); 
		
	}
	void mdf(int x,int y) {
		a[x]=y; 
		t.upd(1,1,n,x,y); 
	}
	pair<ll,int> qry() {
		return t.qry(); 
	}
} line[2]; 
void works() {
	line[0].rd();
	line[1].rd();
	int m=read();
	while(m--) {
		int o=read(),x=read(),y=read();
		line[o-1].mdf(x,y); 
		// cerr<<line[0].qry().first<<' '<<line[1].qry().first<<endl;
		if(line[0].qry()==line[1].qry()) printf("YES\n"); 
		else printf("NO\n"); 
	} 

}
	
signed main() {
	freopen("e.in","r",stdin);
	freopen("e.out","w",stdout);
	int T=1;
	while(T--) {
		works(); 
	}

	return 0; 
}


詳細信息

Test #1:

score: 0
Dangerous Syscalls

input:

5
1 2 3 4 5
5
5 4 3 2 1
8
1 1 5
1 4 2
1 2 4
1 5 1
1 5 5
2 1 4
2 3 5
2 5 5

output:


result: