oj.uz

Submission #750446

# Submission time Handle Problem Language Result Execution time Memory
750446 2023-05-29T14:08:57 Z MrM7md Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 7784 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<<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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 6 ms 432 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 6 ms 484 KB Output is correct
5 Correct 7 ms 604 KB Output is correct
6 Correct 5 ms 600 KB Output is correct
7 Correct 6 ms 596 KB Output is correct
8 Correct 6 ms 596 KB Output is correct
9 Correct 8 ms 596 KB Output is correct
10 Correct 6 ms 596 KB Output is correct
11 Correct 7 ms 596 KB Output is correct
12 Correct 6 ms 596 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5056 ms 3940 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 688 KB Output is correct
2 Correct 17 ms 2400 KB Output is correct
3 Correct 20 ms 2496 KB Output is correct
4 Correct 40 ms 1552 KB Output is correct
5 Correct 67 ms 5104 KB Output is correct
6 Correct 70 ms 5072 KB Output is correct
7 Execution timed out 5064 ms 5076 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 4120 KB Output is correct
2 Correct 109 ms 4140 KB Output is correct
3 Correct 192 ms 3656 KB Output is correct
4 Correct 123 ms 2852 KB Output is correct
5 Correct 189 ms 7580 KB Output is correct
6 Correct 238 ms 7668 KB Output is correct
7 Correct 185 ms 7668 KB Output is correct
8 Correct 300 ms 7784 KB Output is correct
9 Correct 244 ms 7668 KB Output is correct
10 Correct 308 ms 7668 KB Output is correct
11 Correct 199 ms 7656 KB Output is correct
12 Correct 421 ms 7680 KB Output is correct