Submission #583371

#	Time	Username	Problem	Language	Result	Execution time	Memory
583371		mosiashvililuka	ZIGZAG (INOI20_zigzag)	C++14	8 / 100	2080 ms	18984 KiB

Main

#include<bits/stdc++.h>
using namespace std;
char tp;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,f[300009],pas,ZX,XC,l,r,z,zz,za;
pair <long long, long long> seg[1200009];
void DO(long long rr, long long z, long long zz){
    seg[rr].first*=z;seg[rr].second*=z;
    seg[rr].second+=zz;
}
void pushdown(long long q, long long w, long long rr){
    if(q!=w){
        DO(rr*2,seg[rr].first,seg[rr].second);
        DO(rr*2+1,seg[rr].first,seg[rr].second);
    }
    seg[rr]={1,0};
}
void upd(long long q, long long w, long long rr){
    if(q>r||w<l) return;
    if(q>=l&&w<=r){
        DO(rr,z,zz);
        return;
    }
    pushdown(q,w,rr);
    upd(q,(q+w)/2,rr*2);
    upd((q+w)/2+1,w,rr*2+1);
}
long long GETIT(long long q){
    seg[0]={1,0};
    q=za+q-1;
    while(q!=0){
        DO(0,seg[q].first,seg[q].second);
        q/=2;
    }
    return seg[0].second;
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a>>tes;
    za=1;
    while(za<a) za*=2;
    for(i=1; i<=a; i++) cin>>f[i];
    for(i=0; i<=za*2; i++){
        seg[i]={1,0};
    }
    for(i=1; i<=a; i++){
        l=r=i;z=1;zz=f[i];
        upd(1,za,1);
    }
    for(t=1; t<=tes; t++){
        cin>>tp;
        if(tp=='*'){
            cin>>c>>d;
            l=c;r=d;z=-1;zz=0;
            upd(1,za,1);
            continue;
        }
        if(tp=='+'){
            cin>>c>>d>>e;
            l=c;r=d;z=1;zz=e;
            upd(1,za,1);
            continue;
        }
        if(tp=='?'){
            cin>>c>>d;pas=0;
            for(i=c; i<=d; i++){
                f[i]=GETIT(i);
            }
            /*cout<<"f: ";
            for(i=c; i<=d; i++) cout<<f[i]<<" ";
            cout<<"\n";*/
            pas=1;
            zx=1;xc=1;
            for(i=d-1; i>=c; i--){
                if(f[i]==f[i+1]){
                    pas++;
                    zx=1;xc=1;
                    continue;
                }
                pas++;
                if(f[i]<f[i+1]){
                    pas+=xc;
                    ZX=xc+1;XC=1;
                    zx=ZX;xc=XC;
                }else{
                    pas+=zx;
                    ZX=1;XC=zx+1;
                    zx=ZX;xc=XC;
                }
            }
            cout<<pas<<"\n";
            continue;
        }
    }
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 42
• Subtask 3: 0 / 35
• Subtask 4: 0 / 15