QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #662145 | #7007. Rikka with Data Structures | pengpeng_fudan | WA | 2450ms | 23468kb | C++23 | 6.0kb | 2024-10-20 21:25:32 | 2024-10-20 21:25:34 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct seg{
#define mx(x) tr[x].mx
#define num(x) tr[x].num
#define tag1(x) tr[x].tag1
#define tag2(x) tr[x].tag2
int n;
struct node{
int mx,num,tag1,tag2;
}tr[400010];
void pushup1(int p,int l,int r){
mx(p)=max(mx(p<<1),mx(p<<1|1));
num(p)=get(p,l,r);
}
int pushup2(int p,int l,int r,int nz){
if(l==r) return mx(p)>=nz;
spread(p,l,r);
int mid=(l+r)>>1;
if(mx(p<<1|1)>=nz) return num(p)-num(p<<1|1)+pushup2(p<<1|1,mid+1,r,nz);
else return pushup2(p<<1,l,mid,nz);
}
int get(int p,int l,int r){
int mid=(l+r)>>1;
return num(p<<1|1)+(mx(p<<1|1)>mx(p)?0:pushup2(p<<1,l,mid,mx(p<<1|1)));
}
void intt(int sz,vector<int>& ve){
n=sz;
build(1,1,n,ve);
}
void build(int p,int l,int r,vector<int>& ve){
mx(p)=num(p)=tag1(p)=tag2(p)=0;
if(l==r) {mx(p)=ve[l];num(p)=1;return;}
int mid=(l+r)>>1;
build(p<<1,l,mid,ve);
build(p<<1|1,mid+1,r,ve);
pushup1(p,l,r);
// cerr<<l<<' '<<r<<' '<<mx(p)<<' '<<num(p)<<'\n';
}
void spread(int p,int l,int r){
if(tag2(p)){
mx(p<<1)=mx(p<<1|1)=tag2(p);
int mid=(l+r)>>1;
num(p<<1)=mid-l+1,num(p<<1|1)=r-mid;
tag1(p<<1)=tag1(p<<1|1)=0;tag2(p<<1)=tag2(p<<1|1)=tag2(p);
tag2(p)=0;
}
if(tag1(p)){
mx(p<<1)+=tag1(p);mx(p<<1|1)+=tag1(p);
tag1(p<<1)+=tag1(p);tag1(p<<1|1)+=tag1(p);
tag1(p)=0;
}
}
void modify(int p,int l,int r,int L,int R,int nz,int t){
if(L<=l&&r<=R){
if(t==1) {mx(p)+=nz;tag1(p)+=nz;}
else {mx(p)=nz,tag1(p)=0;tag2(p)=nz;num(p)=r-l+1;}
return ;
}
spread(p,l,r);
int mid=(l+r)>>1;
if(mid>=L) modify(p<<1,l,mid,L,R,nz,t);
if(mid<R) modify(p<<1|1,mid+1,r,L,R,nz,t);
pushup1(p,l,r);
}
void modify(int l,int r,int nz,int t){
modify(1,1,n,l,r,nz,t);
}
pair<int,int> queryL(int p,int l,int r,int L,int R,int nz){
if(l==r){
if(mx(p)>nz) return {l,mx(p)};
else return {-1,-1};
}
spread(p,l,r);
int mid=(l+r)>>1;
if(mid<R&&mx(p)>nz){
pair<int,int> t=queryL(p<<1|1,mid+1,r,L,R,nz);
if(t.first!=-1) return t;
}
return queryL(p<<1,l,mid,L,R,nz);
}
pair<int,int> queryL(int l,int nz){
return queryL(1,1,n,1,l,nz);
}
pair<int,int> query_stack_num(int p,int l,int r,int L,int R,int nz){
if(L<=l&&r<=R) return {mx(p),pushup2(p,l,r,nz)};
int mid=(l+r)>>1;
spread(p,l,r);
if(mid>=L&&mid<R) {
pair<int,int> nxtr=query_stack_num(p<<1|1,mid+1,r,L,R,nz);
pair<int,int> nxtl=query_stack_num(p<<1,l,mid,L,R,max(nxtr.first,nz));
return {max(nxtr.first,nxtl.first),nxtr.second+nxtl.second};
}
if(mid>=L) return query_stack_num(p<<1,l,mid,L,R,nz);
if(mid<R) return query_stack_num(p<<1|1,mid+1,r,L,R,nz);
assert(0);
return {-1,-1};
}
int query_stack_num(int l,int r,int nz){
return query_stack_num(1,1,n,l,r,nz).second;
}
int get_num(int p,int l,int r,int pz){
if(l==r) return mx(p);
spread(p,l,r);
int mid=(l+r)>>1;
if(mid>=pz) return get_num(p<<1,l,mid,pz);
else return get_num(p<<1|1,mid+1,r,pz);
}
int get_num(int pz){
return get_num(1,1,n,pz);
}
int ask(int p,int l,int r,int L,int R){
if(L<=l&&r<=R) return mx(p);
spread(p,l,r);
int mid=(l+r)>>1;
if(mid>=L&&mid<R) return max(ask(p<<1,l,mid,L,R),ask(p<<1|1,mid+1,r,L,R));
if(mid>=L) return ask(p<<1,l,mid,L,R);
if(mid<R) return ask(p<<1|1,mid+1,r,L,R);
return -1;
}
int ask(int l,int r){
return ask(1,1,n,l,r);
}
}sg1,sg2;
void solve(){
int n,q;
cin>>n>>q;
vector<int> a1(n+1),a2(n+1);
for(int i=1;i<=n;i++) {cin>>a1[i];a2[n-i+1]=a1[i];}
sg1.intt(n,a1);sg2.intt(n,a2);
for(int i=1;i<=q;i++){
int op,l,r,x;
cin>>op>>l>>r>>x;
if(op==1||op==2) sg1.modify(l,r,x,op),sg2.modify(n-r+1,n-l+1,x,op);
else{
int ans=(l<=x&&x<=r);
auto get1=[&](int lo,int ro,int x)->int {
int res=0;
auto [pz,nz]=sg1.queryL(x-1,sg1.get_num(x));
if(pz<=r) {
res+=max(0ll,ro-max(lo,pz)+1);
if(pz>lo) res+=sg1.query_stack_num(lo,pz-1,nz);
}
else res+=sg1.query_stack_num(lo,ro,sg1.ask(ro+1,x));
return res;
};
auto get2=[&](int lo,int ro,int x)->int {
int res=0;
auto [pz,nz]=sg2.queryL(x-1,sg2.get_num(x));
if(pz<=r) {
res+=max(0ll,ro-max(lo,pz)+1);
if(pz>lo) res+=sg2.query_stack_num(lo,pz-1,nz);
}
else res+=sg2.query_stack_num(lo,ro,sg2.ask(ro+1,x));
return res;
};
int lo=l,ro=min(r,x-1);
if(lo<=ro) ans+=get1(lo,ro,x);
lo=max(x+1,lo),ro=r;
if(lo<=ro) ans+=get2(n-ro+1,n-lo+1,n-x+1);
cout<<ans<<'\n';
}
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int _ = 1;
cin >> _;
while (_--) solve();
return 0;
}
/*
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
*/
/*
1
10 3
1 1 2 3 1 2 3 1 1 2
2 2 3 3 3 2 3 1 1 2
2 3 5 3
1 1 2 1
3 1 5 10
*/
/*
1
10 1
1 3 2 5 2 3 1 6 4 5
3 1 2 10
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5572kb
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: 2450ms
memory: 23468kb
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:
1 59 70 2 2 1 50 5 9 149 58 189 97 247 106 103 43 335 18 87 165 13 78 20 101 5 20 0 5 148 60 0 62 85 171 64 60 33 121 56 0 42 20 167 15 142 15 152 114 28 123 35 219 235 110 120 117 0 0 239 7 104 41 19 104 75 2 114 240 39 143 196 15 0 70 42 93 87 212 4 0 119 103 86 85 52 5 26 41 24 11 74 0 128 20 128...
result:
wrong answer 23rd lines differ - expected: '68', found: '78'