제출 #317291

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
317291		BJoozz	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	747 ms	35108 KiB

sterilizing

#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';
        }
    }

}

컴파일 시 표준 에러 (stderr) 메시지

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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75