제출 #750446

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
750446		MrM7md	Sterilizing Spray (JOI15_sterilizing)	C++17	80 / 100	5064 ms	7784 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define F first
#define S second
#define pb push_back
#define all(a) a.begin(),a.end()
const int N=3e5;
const int off=(1<<20);
const int MOD = 1e9+7;

int t[off*2];
void upd(int x,int v){
   x+=off;
   t[x]=v;
   while(x/=2){
      t[x]=t[x*2]+t[x*2+1];
   }
}
int get(int x,int l,int r,int st,int en){
   if(l>en||r<st)return 0;
   if(l>=st&&r<=en)return t[x];
   int md=(l+r)/2;
   return get(x*2,l,md,st,en)+get(x*2+1,md+1,r,st,en);
}
signed main(){
   ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
   int n,q,k;
   cin >>n >> q >> k;
   int a[n];
   set<int>st;
   for(int i=0;i<n;i++){
      cin >> a[i];
      upd(i,a[i]);
      if(a[i])
      st.insert(i);
   }

   while(q--){
      int ty,x,y;
      cin >> ty >> x >>  y;
      if(ty==1){
         x--;
         upd(x,y);
         a[x]=y;
         if(a[x]){
            st.insert(x);
         }
      }

      if(ty==2){
         x--,y--;

         while(x<=y){
            auto it=st.lower_bound(x);
            if(it==st.end()||*it>y)break;
            x=*it;

            a[x]/=k;
            if((a[x])==0){
               st.erase(x);
               upd(x,0);
            }
            else{
               upd(x,a[x]);
            }
            x++;
         }
      }
      if(ty==3){
         cout<<get(1,1,off-1,x,y)<<endl;
      }
   }
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 75 / 75