제출 #317291

#제출 시각아이디문제언어결과실행 시간메모리
317291BJoozzSterilizing Spray (JOI15_sterilizing)C++14
100 / 100
747 ms35108 KiB
#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++){
      |                     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...