QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#516688 | #6815. Hysteretic Racing | yjf1225 | WA | 693ms | 32692kb | C++14 | 4.7kb | 2024-08-12 20:34:05 | 2024-08-12 20:34:08 |
Judging History
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'