| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1041930 |
2024-08-02T10:28:45 Z |
PM1 |
ZIGZAG (INOI20_zigzag) |
C++17 |
|
738 ms |
76016 KB |
#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define ll long long
const int mxn=3e5+5,szz=(1<<20);
int n,q,a[mxn];
bool aval=0;
ll akhar,fakhar,bakhar,ans;
struct segment{
ll res[szz],rast[szz],chap[szz],lazysum[szz],lazy[szz],brast[szz],bchap[szz],frast[szz],fchap[szz];
void getm(int id,int L,int R){
if(!aval){
aval=1;
akhar=rast[id];
bakhar=brast[id];
fakhar=frast[id];
ans=res[id];
}
else{
int cnt=0;
//cout<<akhar<<" "<<chap[id]<<'\n';
if(fakhar<=akhar && akhar>chap[id] && chap[id]<=fchap[id]){
ans+=bakhar*bchap[id];
if(brast[id]==R-L)
cnt=1;
}
if(fakhar>=akhar && akhar<chap[id] && chap[id]>=fchap[id]){
ans+=bakhar*bchap[id];
if(brast[id]==R-L)
cnt=1;
}
fakhar=(R-L==1)?akhar:frast[id];
akhar=rast[id];
ans+=res[id];
bakhar=(cnt)?bakhar+brast[id]:brast[id];
}
}
void shift(int id){
for(int x=id*2;x<=id*2+1;x++){
rast[x]*=(lazy[id])?-1:1;
chap[x]*=(lazy[id])?-1:1;
rast[x]+=lazysum[id];
chap[x]+=lazysum[id];
frast[x]*=(lazy[id])?-1:1;
fchap[x]*=(lazy[id])?-1:1;
frast[x]+=lazysum[id];
fchap[x]+=lazysum[id];
lazysum[x]*=(lazy[id])?-1:1;
lazysum[x]+=lazysum[id];
lazy[x]^=lazy[id];
}
lazysum[id]=lazy[id]=0;
}
void merge(int id,int L,int R,int mid){
rast[id]=rast[id*2+1];
chap[id]=chap[id*2];
frast[id]=(R-mid==1)?rast[id*2]:frast[id*2+1];
fchap[id]=(mid-L==1)?chap[id*2+1]:fchap[id*2];
res[id]=res[id*2]+res[id*2+1];
brast[id]=brast[id*2+1];
bchap[id]=bchap[id*2];
if(frast[id*2]<=rast[id*2] && rast[id*2]>chap[id*2+1] && chap[id*2+1]<=fchap[id*2+1]){
res[id]+=brast[id*2]*bchap[id*2+1];
if(brast[id*2+1]==R-mid)
brast[id]+=brast[id*2];
if(bchap[id*2]==mid-L)
bchap[id]+=bchap[id*2+1];
}
if(frast[id*2]>=rast[id*2] && rast[id*2]<chap[id*2+1] && chap[id*2+1]>=fchap[id*2+1]){
res[id]+=brast[id*2]*bchap[id*2+1];
if(brast[id*2+1]==R-mid)
brast[id]+=brast[id*2];
if(bchap[id*2]==mid-L)
bchap[id]+=bchap[id*2+1];
}
}
void add(int id,int L,int R,int l,int r,int x){
if(l>=R || L>=r)
return ;
if(l<=L && R<=r){
lazysum[id]+=x;
rast[id]+=x;
chap[id]+=x;
frast[id]+=x;
fchap[id]+=x;
if(L+1==R){
brast[id]=bchap[id]=1;
res[id]=1;
}
return ;
}
int mid=(L+R)>>1;
shift(id);
add(id*2,L,mid,l,r,x);
add(id*2+1,mid ,R,l,r,x);
merge(id,L,R,mid);
return ;
}
void up(int id,int L,int R,int l,int r){
if(l>=R || L>=r)
return ;
if(l<=L && R<=r){
lazysum[id]*=-1;
rast[id]*=-1;
chap[id]*=-1;
frast[id]*=-1;
fchap[id]*=-1;
lazy[id]^=1;
return ;
}
int mid=(L+R)>>1;
shift(id);
up(id*2,L,mid,l,r);
up(id*2+1,mid, R,l,r);
merge(id,L,R,mid);
return ;
}
void get(int id,int L,int R,int l,int r){
if(l>=R || L>=r)
return ;
if(l<=L && R<=r){
getm(id,L,R);
return ;
}
int mid=(L+R)>>1;
shift(id);
get(id*2,L,mid,l,r);
get(id*2+1,mid, R,l,r);
merge(id,L,R,mid);
return ;
}
}seg;
int main(){
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
seg.add(1,1,n+1,i,i+1,a[i]);
}
while(q--){
int l,r,z;
char ty;
cin>>ty;
if(ty=='\\')
cin>>ty;
cin>>l>>r;
if(ty=='+'){
cin>>z;
seg.add(1,1,n+1,l,r+1,z);
}
else if(ty=='?'){
aval=0;
seg.get(1,1,n+1,l,r+1);
cout<<ans<<'\n';
}
else{
seg.up(1,1,n+1,l,r+1);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
7512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
738 ms |
76016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
7512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
7512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
