QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#516688#6815. Hysteretic Racingyjf1225WA 693ms32692kbC++144.7kb2024-08-12 20:34:052024-08-12 20:34:08

Judging History

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

  • [2024-08-12 20:34:08]
  • 评测
  • 测评结果:WA
  • 用时:693ms
  • 内存:32692kb
  • [2024-08-12 20:34:05]
  • 提交

answer

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
namespace Y{
	const long long N=2e5+10;
	
	long long d[N];
	struct Node{
		long long maxx,sum_max,sum_d,ans;
		long long flag,flag2;
	}tree[4*N];
	long long Sum,maxx,ans;
	
	long long find_sum_maxx(long long k,long long maxx,long long l,long long r){
		if(l==r) return max(maxx,tree[k].maxx);
		long long mid=(l+r)>>1;
		if(tree[2*k].maxx<=maxx){
			return (mid-l+1)*maxx+find_sum_maxx(2*k+1,maxx,mid+1,r);
		}
		else{
			return find_sum_maxx(2*k,maxx,l,mid)+tree[k].sum_max-tree[2*k].sum_max;
		}
	}
	
	long long find_ans(long long k,long long maxx,long long l,long long r){
		if(l==r) return max(tree[k].maxx,maxx)*tree[k].sum_d;
		long long mid=(l+r)>>1;
		if(tree[2*k].maxx<=maxx){
			return tree[2*k].sum_d*maxx+find_ans(2*k+1,maxx,mid+1,r);
		}
		else{
			return find_ans(2*k,maxx,l,mid)+tree[k].ans-tree[2*k].ans;
		}
	}
	
	void up(long long k,long long l,long long mid,long long r){
		tree[k].maxx=max(tree[2*k].maxx,tree[2*k+1].maxx);
		tree[k].sum_d=tree[2*k].sum_d+tree[2*k+1].sum_d;
		tree[k].ans=tree[2*k].ans+find_ans(2*k+1,tree[2*k].maxx,mid+1,r);
		tree[k].sum_max=tree[2*k].sum_max+find_sum_maxx(2*k+1,tree[2*k].maxx,mid+1,r);
	}
	
	void down_(long long k,long long d,long long l,long long r){
		if(d!=0){ //要区间赋值!!! 
			tree[k].ans=d*d*(r-l+1);
			tree[k].sum_max=(r-l+1)*d;
			tree[k].sum_d=(r-l+1)*d;
			tree[k].maxx=d;
			
			tree[k].flag=d;
			tree[k].flag2=0;
		}
	}
	
	void down_2(long long k,long long d,long long l,long long r){
		tree[k].ans+=(tree[k].sum_max+tree[k].sum_d)*d+d*d*(r-l+1);
		tree[k].sum_max+=(r-l+1)*d;
		tree[k].sum_d+=(r-l+1)*d;
		tree[k].maxx+=d;
		
		tree[k].flag2+=d;
	}
	
	void down(long long k,long long l,long long mid,long long r){
		down_(2*k,tree[k].flag,l,mid);
		down_(2*k+1,tree[k].flag,mid+1,r);
		tree[k].flag=0;
		down_2(2*k,tree[k].flag2,l,mid);
		down_2(2*k+1,tree[k].flag2,mid+1,r);
		tree[k].flag2=0;
	}
	
	void build(long long k,long long l,long long r){
		if(l==r){
			tree[k].sum_max=tree[k].sum_d=tree[k].maxx=d[l];
			tree[k].ans=d[l]*d[l];
			return ;
		}
		long long mid=(l+r)>>1;
//		down(k,l,mid,r);
		build(2*k,l,mid);
		build(2*k+1,mid+1,r);
		up(k,l,mid,r);
	}
	
	void modify1(long long k,long long l,long long r,long long L,long long R,long long d){
		if(r<L || R<l) return ;
		if(L<=l && r<=R){
			down_2(k,d,l,r);
			return ;
		}
		long long mid=(l+r)>>1;
		down(k,l,mid,r);
		modify1(2*k,l,mid,L,R,d);
		modify1(2*k+1,mid+1,r,L,R,d);
		up(k,l,mid,r);
	}
	
	void modify2(long long k,long long l,long long r,long long L,long long R,long long d){
		if(r<L || R<l) return ;
		if(L<=l && r<=R){
			down_(k,d,l,r);
			return ;
		}
		long long mid=(l+r)>>1;
		down(k,l,mid,r);
		modify2(2*k,l,mid,L,R,d);
		modify2(2*k+1,mid+1,r,L,R,d);
		up(k,l,mid,r);
	}
	
	void query2(long long k,long long l,long long r){
		long long tmp=find_ans(k,maxx,l,r);
		if(Sum-tmp>=0){
			Sum-=tmp;
			maxx=max(maxx,tree[k].maxx);
			return ;
		}
		if(l==r){
			Sum-=tmp;
			ans=l;
			return ;
		}
		long long mid=(l+r)>>1;
		down(k,l,mid,r);
		query2(2*k,l,mid);
		if(Sum<0) return ;
		query2(2*k+1,mid+1,r);
//		up(k,l,mid,r);
	}
	
	void query(long long k,long long l,long long r,long long L,long long R){
		if(r<L || R<l) return ;
		if(L<=l && r<=R){
			query2(k,l,r);
			return ;
		}
		long long mid=(l+r)>>1;
		down(k,l,mid,r);
		query(2*k,l,mid,L,R);
		if(Sum<0) return ;
		query(2*k+1,mid+1,r,L,R);
//		up(k,l,mid,r);
	}
	
	signed main(){
		long long n,t;
		cin>>n>>t;
		
		for(long long i=0;i<n;i++){
			scanf("%lld",&d[i]);
		}
		
		build(1,0,n-1);
		
		char op[2];long long x,y,z;
		while(t--){
			scanf("%s",op);
			if(op[0]=='P'){
				scanf("%lld%lld%lld",&x,&y,&z);
//				for(int i=x;;i=(i+1)%n){
//					d[i]+=z;
//					if(i==y) break;
//				}
				if(x<=y) modify1(1,0,n-1,x,y,z);
				else modify1(1,0,n-1,x,n-1,z),modify1(1,0,n-1,0,y,z);
//				build(1,0,n-1);
			}
			else if(op[0]=='R'){
				scanf("%lld%lld%lld",&x,&y,&z);
//				for(int i=x;;i=(i+1)%n){
//					d[i]=z;
//					if(i==y) break;
//				}
				if(x<=y) modify2(1,0,n-1,x,y,z);
				else modify2(1,0,n-1,x,n-1,z),modify2(1,0,n-1,0,y,z);
//				build(1,0,n-1);
			}
			else{
				scanf("%lld%lld",&x,&y);
				Sum=y;maxx=0;
				query(1,0,n-1,x,n-1);
//				cout<<"???"<<Sum<<' '<<maxx<<'\n';
				if(Sum<0){
					printf("%lld\n",ans);
					continue;
				}
				query(1,0,n-1,0,n-1);
				if(Sum<0){
					printf("%lld\n",ans);
					continue;
				}
				Sum%=tree[1].maxx*tree[1].sum_d;
//				cout<<"!!!"<<Sum<<'\n';
				query(1,0,n-1,0,n-1);
				printf("%lld\n",ans);
			}
		}
		
		return 0;
	}
}
signed main(){
	return Y::main();
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 5932kb

input:

2 4
1 2
Q 0 0
Q 0 1
Q 0 4
Q 0 5

output:

0
1
1
0

result:

ok 4 tokens

Test #2:

score: 0
Accepted
time: 1ms
memory: 5800kb

input:

5 7
2 5 1 4 3
Q 3 28
Q 0 39
P 4 0 3
Q 2 60
R 4 1 2
Q 1 22
Q 3 19260817

output:

0
3
0
4
1

result:

ok 5 tokens

Test #3:

score: -100
Wrong Answer
time: 693ms
memory: 32692kb

input:

200000 200000
613996 961471 536170 309149 407021 455240 358488 991078 61893 884024 149317 850785 867113 399303 403939 212239 258081 876122 195526 807123 889530 372732 596978 400631 815703 133663 994909 547857 947107 647857 602092 850543 843740 124903 157661 328300 638794 447455 172285 834119 422682 ...

output:

81822
121278
143252
126362
17062
178855
86673
68466
127080
650
115616
28947
175295
82801
176475
70500
1073
109186
44224
54918
99964
28253
122947
25532
14288
176339
142311
142401
35241
191326
80126
88346
53523
20320
33237
129748
6725
16808
199129
28459
21301
124350
22441
170717
139180
62786
180834
12...

result:

wrong answer 5th words differ - expected: '16581', found: '17062'