| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1042055 |
2024-08-02T13:33:45 Z |
PM1 |
ZIGZAG (INOI20_zigzag) |
C++17 |
|
816 ms |
84424 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(akhar>chap[id]){
if(fakhar<=akhar && chap[id]<=fchap[id]){
ans+=bakhar*bchap[id];
if(brast[id]==R-L)
cnt=1;
}
else if(fakhar<=akhar){
ans+=bakhar;
}
else if(chap[id]<=fchap[id]){
ans+=bchap[id];
if(brast[id]==R-L)
cnt=2;
}
}
if(akhar<chap[id]){
if(fakhar>=akhar && chap[id]>=fchap[id]){
ans+=bakhar*bchap[id];
if(brast[id]==R-L)
cnt=1;
}
else if(fakhar>=akhar){
ans+=bakhar;
}
else if(chap[id]>=fchap[id]){
ans+=bchap[id];
if(brast[id]==R-L)
cnt=2;
}
}
fakhar=(R-L==1)?akhar:frast[id];
akhar=rast[id];
ans+=res[id];
bakhar=(cnt==1)?bakhar+brast[id]:brast[id];
if(cnt==2)
bakhar++;
}
}
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(rast[id*2]>chap[id*2+1]){
//cout<<chap[id*2+1]<<" "<<fchap[id*2+1]<<'\n';
if(frast[id*2]<=rast[id*2] && 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];
}
else if(frast[id*2]<=rast[id*2]){
res[id]+=brast[id*2];
if(bchap[id*2]==mid-L)
bchap[id]++;
}
else if(chap[id*2+1]<=fchap[id*2+1]){
res[id]+=bchap[id*2+1];
if(brast[id*2+1]==R-mid)
brast[id]++;
}
else
res[id]++;
//cout<<" "<<L<<" "<<R<<"" <<res[id]<<''
}
else if(rast[id*2]<chap[id*2+1]){
if(frast[id*2]>=rast[id*2] && 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];
}
else if(frast[id*2]>=rast[id*2]){
res[id]+=brast[id*2];
if(bchap[id*2]==mid-L)
bchap[id]++;
}
else if(chap[id*2+1]>=fchap[id*2+1]){
res[id]+=bchap[id*2+1];
if(brast[id*2+1]==R-mid)
brast[id]++;
}
else
res[id]++;
}
}
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 |
11 ms |
7516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
712 ms |
79188 KB |
Output is correct |
| 2 |
Correct |
159 ms |
8784 KB |
Output is correct |
| 3 |
Correct |
702 ms |
84304 KB |
Output is correct |
| 4 |
Correct |
816 ms |
84332 KB |
Output is correct |
| 5 |
Correct |
697 ms |
84304 KB |
Output is correct |
| 6 |
Correct |
731 ms |
84324 KB |
Output is correct |
| 7 |
Correct |
714 ms |
81140 KB |
Output is correct |
| 8 |
Correct |
747 ms |
84308 KB |
Output is correct |
| 9 |
Correct |
695 ms |
84424 KB |
Output is correct |
| 10 |
Correct |
615 ms |
84404 KB |
Output is correct |
| 11 |
Correct |
707 ms |
84392 KB |
Output is correct |
| 12 |
Correct |
759 ms |
84260 KB |
Output is correct |
| 13 |
Correct |
594 ms |
84304 KB |
Output is correct |
| 14 |
Correct |
580 ms |
84304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
7516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
7516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
