oj.uz

Submission #317291

# Submission time Handle Problem Language Result Execution time Memory
317291 2020-10-29T10:19:06 Z BJoozz Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 747 ms 35108 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);
}
ll F[MAX];
void  UPD(int id,int val){
    for(;id<MAX;id+=id&-id) F[id]+=val;
}
ll  GET(int id){
    ll res=0;
    for(;id>0;id-=id&-id) res+=F[id];
    return res;
}
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;
    if(K==1){
        for(int i=1,x;i<=n;i++){
            cin>>a[i];
            UPD(i,a[i]);
        }
            int t,x,y;
            while(Q--){
                cin>>t>>x>>y;
                if(t==1){
                    UPD(x,y-a[x]);a[x]=y;
                }
                else{
                    if(t==3)
                    cout<<GET(y)-GET(x-1)<<'\n';
                }
            }
        return 0;
    }
    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;
      |             ~^~
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:107:21: warning: unused variable 'x' [-Wunused-variable]
  107 |         for(int i=1,x;i<=n;i++){
      |                     ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2944 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 4 ms 3456 KB Output is correct
4 Correct 8 ms 3456 KB Output is correct
5 Correct 10 ms 3968 KB Output is correct
6 Correct 10 ms 3968 KB Output is correct
7 Correct 10 ms 3968 KB Output is correct
8 Correct 10 ms 3968 KB Output is correct
9 Correct 10 ms 3968 KB Output is correct
10 Correct 11 ms 3968 KB Output is correct
11 Correct 10 ms 3968 KB Output is correct
12 Correct 10 ms 3968 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 3704 KB Output is correct
2 Correct 40 ms 3648 KB Output is correct
3 Correct 32 ms 3960 KB Output is correct
4 Correct 40 ms 4216 KB Output is correct
5 Correct 48 ms 4344 KB Output is correct
6 Correct 54 ms 4472 KB Output is correct
7 Correct 51 ms 4344 KB Output is correct
8 Correct 49 ms 4344 KB Output is correct
9 Correct 46 ms 4344 KB Output is correct
10 Correct 47 ms 4344 KB Output is correct
11 Correct 47 ms 4344 KB Output is correct
12 Correct 49 ms 4344 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 4864 KB Output is correct
2 Correct 125 ms 19064 KB Output is correct
3 Correct 167 ms 18848 KB Output is correct
4 Correct 367 ms 11000 KB Output is correct
5 Correct 711 ms 34836 KB Output is correct
6 Correct 708 ms 34812 KB Output is correct
7 Correct 39 ms 4088 KB Output is correct
8 Correct 709 ms 34936 KB Output is correct
9 Correct 459 ms 34680 KB Output is correct
10 Correct 472 ms 34680 KB Output is correct
11 Correct 464 ms 34680 KB Output is correct
12 Correct 455 ms 34684 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 19000 KB Output is correct
2 Correct 431 ms 19064 KB Output is correct
3 Correct 284 ms 19004 KB Output is correct
4 Correct 388 ms 11128 KB Output is correct
5 Correct 716 ms 35064 KB Output is correct
6 Correct 720 ms 34936 KB Output is correct
7 Correct 719 ms 34936 KB Output is correct
8 Correct 747 ms 35108 KB Output is correct
9 Correct 475 ms 34936 KB Output is correct
10 Correct 486 ms 35080 KB Output is correct
11 Correct 466 ms 34936 KB Output is correct
12 Correct 490 ms 35064 KB Output is correct