oj.uz

답안 #317288

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
317288 2020-10-29T09:59:59 Z BJoozz Sterilizing Spray (JOI15_sterilizing) C++14
0 / 100
 449 ms 20472 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;
        }
        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;
    }
    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:34:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     int mid=l+r>>1;
      |             ~^~
sterilizing.cpp: In function 'void upd(int, int, int, int, int)':
sterilizing.cpp:57:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |     int mid=l+r>>1;
      |             ~^~
sterilizing.cpp: In function 'll get(int, int, int, int, int)':
sterilizing.cpp:79:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |     int mid=l+r>>1;
      |             ~^~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 2944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 111 ms 5496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 449 ms 20472 KB Output isn't correct
2 Halted 0 ms 0 KB -