oj.uz

Submission #750451

# Submission time Handle Problem Language Result Execution time Memory
750451 2023-05-29T14:12:55 Z MrM7md Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 7752 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){
         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 5 ms 340 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 7 ms 468 KB Output is correct
5 Correct 7 ms 468 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 6 ms 572 KB Output is correct
8 Correct 8 ms 572 KB Output is correct
9 Correct 10 ms 468 KB Output is correct
10 Correct 9 ms 468 KB Output is correct
11 Correct 6 ms 468 KB Output is correct
12 Correct 6 ms 572 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 596 KB Output is correct
2 Correct 17 ms 2416 KB Output is correct
3 Correct 23 ms 2508 KB Output is correct
4 Correct 41 ms 1528 KB Output is correct
5 Correct 73 ms 5028 KB Output is correct
6 Correct 66 ms 5092 KB Output is correct
7 Execution timed out 5027 ms 5040 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 4064 KB Output is correct
2 Correct 101 ms 4216 KB Output is correct
3 Correct 168 ms 3624 KB Output is correct
4 Correct 111 ms 2864 KB Output is correct
5 Correct 183 ms 7640 KB Output is correct
6 Correct 218 ms 7540 KB Output is correct
7 Correct 174 ms 7732 KB Output is correct
8 Correct 290 ms 7632 KB Output is correct
9 Correct 239 ms 7632 KB Output is correct
10 Correct 289 ms 7752 KB Output is correct
11 Correct 192 ms 7668 KB Output is correct
12 Correct 412 ms 7664 KB Output is correct