oj.uz

Submission #317290

# Submission time Handle Problem Language Result Execution time Memory
317290 2020-10-29T10:11:29 Z BJoozz Sterilizing Spray (JOI15_sterilizing) C++14
75 / 100
 737 ms 35152 KB 
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
using ll = long long ;
//#define int long long

using ii = pair < int , int > ;
const int MAX = 1e5+4,mod=1e9+7;
const int inf=0x3f3f3f3f;
int K;
vector < ii > pr[MAX];
void minn(int &a , int b){
if(b<a) a=b;
}
void maxx(int &a , int b){
if(b>a) a=b;
}
int LZ[MAX*4];
int ST[30][MAX*4];
int val;
int a[MAX];
void up (int x,int id,int l,int r){

    if(l==r){
        int z=0;
        while(val!=0){
            ST[z++][id]=val%K;
            val/=K;
        }
        for(z;z<30;z++) ST[z][id]=0;
        return;
    }
    int mid=l+r>>1;
    if(LZ[id]){
        minn(LZ[id],30);
        LZ[id<<1]+=LZ[id];
        LZ[id<<1|1]+=LZ[id];
        for(int i=0;i<30-LZ[id];i++) ST[i][id<<1]=ST[i+LZ[id]][id<<1],ST[i][id<<1|1]=ST[i+LZ[id]][id<<1|1];;
        for(int i=30-LZ[id];i<30;i++) ST[i][id<<1]=ST[i][id<<1|1]=0;
        LZ[id]=0;
    }
    if(x>mid) up(x,id<<1|1,mid+1,r);
    else up(x,id<<1,l,mid);
    for(int i=29;i>=0;i--) ST[i][id]=ST[i][id<<1]+ST[i][id<<1|1];

}
void upd (int x,int y,int id,int l,int r){
    if(y<l || x>r) return;
    if(x<=l && r<=y){
        for(int i=0;i<29;i++)
            ST[i][id]=ST[i+1][id];
        ST[29][id]=0;
        LZ[id]++;
        return;
    }
    int mid=l+r>>1;
    if(LZ[id]){
        minn(LZ[id],30);
        LZ[id<<1]+=LZ[id];
        LZ[id<<1|1]+=LZ[id];
        for(int i=0;i<30-LZ[id];i++) ST[i][id<<1]=ST[i+LZ[id]][id<<1],ST[i][id<<1|1]=ST[i+LZ[id]][id<<1|1];;
        for(int i=30-LZ[id];i<30;i++) ST[i][id<<1]=ST[i][id<<1|1]=0;
        LZ[id]=0;
    }
    upd(x,y,id<<1,l,mid);
    upd(x,y,id<<1|1,mid+1,r);
    for(int i=29;i>=0;i--) ST[i][id]=ST[i][id<<1]+ST[i][id<<1|1];
}
ll P[30];
ll get(int x,int y,int id,int l,int r){
    if(y<l || x>r) return 0;
    if(x<=l && r<=y){
        ll res=0;
        for(int i=0;i<30;i++)
            res+=P[i]*ST[i][id];
        return res;
    }
    int mid=l+r>>1;
    if(LZ[id]){
        minn(LZ[id],30);
        LZ[id<<1]+=LZ[id];
        LZ[id<<1|1]+=LZ[id];
        for(int i=0;i<30-LZ[id];i++) ST[i][id<<1]=ST[i+LZ[id]][id<<1],ST[i][id<<1|1]=ST[i+LZ[id]][id<<1|1];;
        for(int i=30-LZ[id];i<30;i++) ST[i][id<<1]=ST[i][id<<1|1]=0;
        LZ[id]=0;
    }
    //for(int i=29;i>=0;i--) ST[i][id]=ST[i][id<<1]+ST[i][id<<1|1];
    return get(x,y,id<<1,l,mid)+get(x,y,id<<1|1,mid+1,r);
}
int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("JOI15.inp", "r", stdin);//freopen("JOI15.out", "w", stdout);
    int n,Q;
    cin>>n>>Q>>K;
    P[0]=1;
    for(int i=1;i<30;i++) P[i]=P[i-1]*K;
    for(int i=1;i<=n;i++) {cin>>val;up(i,1,1,n);}
    int t,x,y;
    while(Q--){
        cin>>t>>x>>y;
        if(t==1){
            val=y;
            up(x,1,1,n);
        }
        else{
            if(t==2)
                upd(x,y,1,1,n);
            else cout<<get(x,y,1,1,n)<<'\n';
        }
    }

}

Compilation message

sterilizing.cpp: In function 'void up(int, int, int, int)':
sterilizing.cpp:32:13: warning: statement has no effect [-Wunused-value]
   32 |         for(z;z<30;z++) ST[z][id]=0;
      |             ^
sterilizing.cpp:35:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     int mid=l+r>>1;
      |             ~^~
sterilizing.cpp: In function 'void upd(int, int, int, int, int)':
sterilizing.cpp:58:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |     int mid=l+r>>1;
      |             ~^~
sterilizing.cpp: In function 'll get(int, int, int, int, int)':
sterilizing.cpp:80:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |     int mid=l+r>>1;
      |             ~^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2944 KB Output is correct
2 Runtime error 9 ms 5632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 5632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 4952 KB Output is correct
2 Correct 129 ms 18808 KB Output is correct
3 Correct 167 ms 18808 KB Output is correct
4 Correct 356 ms 10872 KB Output is correct
5 Correct 734 ms 34940 KB Output is correct
6 Correct 710 ms 34844 KB Output is correct
7 Runtime error 9 ms 5632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 19016 KB Output is correct
2 Correct 447 ms 19132 KB Output is correct
3 Correct 282 ms 19064 KB Output is correct
4 Correct 382 ms 11172 KB Output is correct
5 Correct 731 ms 34964 KB Output is correct
6 Correct 713 ms 34940 KB Output is correct
7 Correct 714 ms 35152 KB Output is correct
8 Correct 737 ms 34936 KB Output is correct
9 Correct 473 ms 34936 KB Output is correct
10 Correct 481 ms 34984 KB Output is correct
11 Correct 473 ms 35064 KB Output is correct
12 Correct 498 ms 34940 KB Output is correct