oj.uz

Submission #750453

# Submission time Handle Problem Language Result Execution time Memory
750453 2023-05-29T14:13:51 Z MrM7md Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 403 ms 7932 KB 
#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<<17);
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&&k>1){
         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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 6 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 6 ms 572 KB Output is correct
8 Correct 6 ms 580 KB Output is correct
9 Correct 7 ms 576 KB Output is correct
10 Correct 6 ms 468 KB Output is correct
11 Correct 5 ms 468 KB Output is correct
12 Correct 6 ms 468 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 4172 KB Output is correct
2 Correct 50 ms 3076 KB Output is correct
3 Correct 61 ms 6024 KB Output is correct
4 Correct 72 ms 7624 KB Output is correct
5 Correct 84 ms 7772 KB Output is correct
6 Correct 87 ms 7760 KB Output is correct
7 Correct 86 ms 7764 KB Output is correct
8 Correct 111 ms 7932 KB Output is correct
9 Correct 77 ms 7824 KB Output is correct
10 Correct 85 ms 7820 KB Output is correct
11 Correct 84 ms 7824 KB Output is correct
12 Correct 77 ms 7744 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 596 KB Output is correct
2 Correct 17 ms 2460 KB Output is correct
3 Correct 19 ms 2464 KB Output is correct
4 Correct 39 ms 1504 KB Output is correct
5 Correct 62 ms 5080 KB Output is correct
6 Correct 60 ms 5056 KB Output is correct
7 Correct 58 ms 5504 KB Output is correct
8 Correct 61 ms 5076 KB Output is correct
9 Correct 60 ms 5036 KB Output is correct
10 Correct 54 ms 5016 KB Output is correct
11 Correct 55 ms 5068 KB Output is correct
12 Correct 63 ms 5028 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 4072 KB Output is correct
2 Correct 102 ms 4148 KB Output is correct
3 Correct 168 ms 3624 KB Output is correct
4 Correct 113 ms 2764 KB Output is correct
5 Correct 189 ms 7556 KB Output is correct
6 Correct 220 ms 7688 KB Output is correct
7 Correct 177 ms 7632 KB Output is correct
8 Correct 288 ms 7648 KB Output is correct
9 Correct 239 ms 7824 KB Output is correct
10 Correct 280 ms 7672 KB Output is correct
11 Correct 199 ms 7628 KB Output is correct
12 Correct 403 ms 7632 KB Output is correct