oj.uz

Submission #583371

# Submission time Handle Problem Language Result Execution time Memory
583371 2022-06-25T09:56:28 Z mosiashvililuka ZIGZAG (INOI20_zigzag) C++14
8 / 100
 2000 ms 18984 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 596 KB Output is correct
2 Correct 82 ms 636 KB Output is correct
3 Correct 82 ms 632 KB Output is correct
4 Correct 83 ms 644 KB Output is correct
5 Correct 83 ms 644 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 233 ms 624 KB Output is correct

Subtask #2
0 / 42.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2080 ms 18984 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 596 KB Output is correct
2 Correct 82 ms 636 KB Output is correct
3 Correct 82 ms 632 KB Output is correct
4 Correct 83 ms 644 KB Output is correct
5 Correct 83 ms 644 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 233 ms 624 KB Output is correct
8 Execution timed out 2074 ms 5208 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 596 KB Output is correct
2 Correct 82 ms 636 KB Output is correct
3 Correct 82 ms 632 KB Output is correct
4 Correct 83 ms 644 KB Output is correct
5 Correct 83 ms 644 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 233 ms 624 KB Output is correct
8 Execution timed out 2080 ms 18984 KB Time limit exceeded
9 Halted 0 ms 0 KB -