QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #288346 | #7007. Rikka with Data Structures | zhouhuanyi | WA | 4360ms | 15740kb | C++20 | 5.0kb | 2023-12-22 15:38:05 | 2023-12-22 15:38:06 |
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].cnt-tree[k<<1|1].cnt;
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: 4196kb
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: 4360ms
memory: 15740kb
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:
25 57 61 190 11 1 36 5 9 139 47 194 18 247 106 103 43 327 18 87 165 13 68 114 101 5 34 152 5 138 58 43 62 112 122 41 81 40 48 47 24 42 34 167 15 98 31 112 114 17 123 35 173 167 106 120 116 63 191 210 37 104 41 48 104 68 2 114 239 29 143 167 15 54 39 42 85 77 212 7 47 96 33 80 83 18 2 57 29 65 11 74 ...
result:
wrong answer 1st lines differ - expected: '1', found: '25'