QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #288356 | #7007. Rikka with Data Structures | zhouhuanyi | WA | 4358ms | 15228kb | C++20 | 5.0kb | 2023-12-22 15:47:46 | 2023-12-22 15:47:47 |
Judging History
answer
#include<iostream>
#include<cstdio>
#define N 100000
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
int Ts,n,m,lg[N+1],A[N+1],tong[N+1],length;
struct seg
{
struct node
{
int l,r,cnt,cnt2,lazych;
long long maxn,lazy;
};
node tree[(N<<2)+1];
void build(int k,int l,int r)
{
tree[k].l=l,tree[k].r=r,tree[k].lazy=tree[k].cnt=tree[k].cnt2=0,tree[k].lazych=-1;
int mid=(l+r)>>1,res=0;
for (int i=l;i<=r;++i) res=max(res,A[i]),tree[k].cnt+=(res==A[i]);
res=0;
for (int i=r;i>=l;--i) res=max(res,A[i]),tree[k].cnt2+=(res==A[i]);
tree[k].maxn=res;
if (l==r) return;
build(k<<1,l,mid),build(k<<1|1,mid+1,r);
return;
}
void push_change(int k,int d)
{
tree[k].maxn=tree[k].lazych=d,tree[k].lazy=0,tree[k].cnt=tree[k].cnt2=tree[k].r-tree[k].l+1;
return;
}
void push_add(int k,long long d)
{
tree[k].maxn+=d,tree[k].lazy+=d;
return;
}
void spread(int k)
{
if (tree[k].lazych!=-1) push_change(k<<1,tree[k].lazych),push_change(k<<1|1,tree[k].lazych),tree[k].lazych=-1;
if (tree[k].lazy) push_add(k<<1,tree[k].lazy),push_add(k<<1|1,tree[k].lazy),tree[k].lazy=0;
return;
}
int calc(int k,long long d)
{
if (tree[k].l==tree[k].r) return tree[k].maxn>=d;
spread(k);
if (d<=tree[k<<1].maxn) return calc(k<<1,d)+tree[k].cnt-tree[k<<1].cnt;
else return calc(k<<1|1,d);
}
int calc2(int k,long long d)
{
if (tree[k].l==tree[k].r) return tree[k].maxn>=d;
spread(k);
if (d<=tree[k<<1|1].maxn) return calc2(k<<1|1,d)+tree[k].cnt2-tree[k<<1|1].cnt2;
else return calc2(k<<1,d);
}
void push_up(int k)
{
tree[k].maxn=max(tree[k<<1].maxn,tree[k<<1|1].maxn),tree[k].cnt=tree[k<<1].cnt+calc(k<<1|1,tree[k<<1].maxn),tree[k].cnt2=tree[k<<1|1].cnt2+calc2(k<<1,tree[k<<1|1].maxn);
return;
}
void add(int k,int l,int r,int d)
{
if (tree[k].l==l&&tree[k].r==r)
{
push_add(k,d);
return;
}
spread(k);
int mid=(tree[k].l+tree[k].r)>>1;
if (r<=mid) add(k<<1,l,r,d);
else if (l>=mid+1) add(k<<1|1,l,r,d);
else add(k<<1,l,mid,d),add(k<<1|1,mid+1,r,d);
push_up(k);
return;
}
void change(int k,int l,int r,int d)
{
if (tree[k].l==l&&tree[k].r==r)
{
push_change(k,d);
return;
}
spread(k);
int mid=(tree[k].l+tree[k].r)>>1;
if (r<=mid) change(k<<1,l,r,d);
else if (l>=mid+1) change(k<<1|1,l,r,d);
else change(k<<1,l,mid,d),change(k<<1|1,mid+1,r,d);
push_up(k);
return;
}
long long get_maxn(int k,int l,int r)
{
if (tree[k].l==l&&tree[k].r==r) return tree[k].maxn;
spread(k);
int mid=(tree[k].l+tree[k].r)>>1;
if (r<=mid) return get_maxn(k<<1,l,r);
else if (l>=mid+1) return get_maxn(k<<1|1,l,r);
else return max(get_maxn(k<<1,l,mid),get_maxn(k<<1|1,mid+1,r));
}
void find(int k,int l,int r)
{
if (tree[k].l==l&&tree[k].r==r)
{
tong[++length]=k;
return;
}
spread(k);
int mid=(tree[k].l+tree[k].r)>>1;
if (r<=mid) find(k<<1,l,r);
else if (l>=mid+1) find(k<<1|1,l,r);
else find(k<<1,l,mid),find(k<<1|1,mid+1,r);
return;
}
};
seg T;
int main()
{
int op,l,r,sl,sr,x,res;
long long d,rst;
for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
Ts=read();
while (Ts--)
{
n=read(),m=read();
for (int i=1;i<=n;++i) A[i]=read();
T.build(1,1,n);
for (int i=1;i<=m;++i)
{
op=read(),l=read(),r=read(),x=read();
if (op==1) T.add(1,l,r,x);
else if (op==2) T.change(1,l,r,x);
else
{
if (l<=x&&x<=r)
{
sl=sr=x,d=T.get_maxn(1,x,x);
for (int j=lg[r-x+1];j>=0;--j)
if (sr+(1<<j)<=r&&T.get_maxn(1,x+1,sr+(1<<j))<=d)
sr+=(1<<j);
for (int j=lg[x-l+1];j>=0;--j)
if (sl-(1<<j)>=l&&T.get_maxn(1,sl-(1<<j),x-1)<=d)
sl-=(1<<j);
res=sr-sl+1;
if (sr+1<=r)
{
rst=d,length=0,T.find(1,sr+1,r);
for (int j=1;j<=length;++j) res+=T.calc(tong[j],rst),rst=max(rst,T.tree[tong[j]].maxn);
}
if (l<=sl-1)
{
rst=d,length=0,T.find(1,l,sl-1);
for (int j=length;j>=1;--j) res+=T.calc2(tong[j],rst),rst=max(rst,T.tree[tong[j]].maxn);
}
printf("%d\n",res);
}
else if (x<l)
{
d=T.get_maxn(1,x,l-1),sr=l-1;
for (int j=lg[r-l+1];j>=0;--j)
if (sr+(1<<j)<=r&&T.get_maxn(1,l,sr+(1<<j))<=d)
sr+=(1<<j);
res=sr-l+1;
if (sr+1<=r)
{
rst=d,length=0,T.find(1,sr+1,r);
for (int j=1;j<=length;++j) res+=T.calc(tong[j],rst),rst=max(rst,T.tree[tong[j]].maxn);
}
printf("%d\n",res);
}
else if (x>r)
{
d=T.get_maxn(1,r+1,x),sl=r+1;
for (int j=lg[r-l+1];j>=0;--j)
if (sl-(1<<j)>=l&&T.get_maxn(1,sl-(1<<j),r)<=d)
sl-=(1<<j);
res=r-sl+1;
if (l<=sl-1)
{
rst=d,length=0,T.find(1,l,sl-1);
for (int j=length;j>=1;--j) res+=T.calc2(tong[j],rst),rst=max(rst,T.tree[tong[j]].maxn);
}
printf("%d\n",res);
}
}
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4300kb
input:
1 10 10 1 3 2 5 2 3 1 6 4 5 3 5 7 8 3 5 7 4 1 1 5 2 3 1 10 4 3 1 10 8 2 8 8 8 3 1 10 8 3 1 10 4 2 4 8 1 3 1 2 10
output:
3 3 10 7 10 8 2
result:
ok 7 lines
Test #2:
score: -100
Wrong Answer
time: 4358ms
memory: 15228kb
input:
200 321 43 168330405 102091681 86278243 227886812 609333939 211045240 332465535 212315420 510322126 700237719 102348318 320419595 409640374 582249257 245617532 643949598 748863235 405762764 358055464 585833725 429993246 60296212 632603910 229141445 696836739 297883078 545245133 44079558 92873286 347...
output:
22 59 70 187 4 84 50 5 9 149 58 189 97 247 106 103 43 335 18 87 165 13 68 114 101 5 34 152 5 148 60 43 62 85 171 64 119 40 121 56 24 42 34 167 15 142 15 152 114 28 123 35 219 235 110 120 117 63 191 239 37 104 41 24 104 75 2 114 240 29 143 196 15 54 70 42 93 87 212 7 47 119 103 86 85 52 5 54 43 65 11...
result:
wrong answer 1st lines differ - expected: '1', found: '22'