oj.uz

Submission #750448

# Submission time Handle Problem Language Result Execution time Memory
750448 2023-05-29T14:10:48 Z MrM7md Sterilizing Spray (JOI15_sterilizing) C++17
0 / 100
 5000 ms 3924 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5048 ms 3216 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 600 KB Output is correct
2 Correct 19 ms 1900 KB Output is correct
3 Correct 26 ms 1972 KB Output is correct
4 Correct 49 ms 1248 KB Output is correct
5 Correct 70 ms 3924 KB Output is correct
6 Correct 70 ms 3900 KB Output is correct
7 Execution timed out 5073 ms 3888 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 112 ms 3532 KB Output isn't correct
2 Halted 0 ms 0 KB -