Submission #128065

#	Time	Username	Problem	Language	Result	Execution time	Memory
128065		mirbek01	Sterilizing Spray (JOI15_sterilizing)	C++11	100 / 100	336 ms	7816 KiB

sterilizing

# include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;

int n, q, k, a[N];
long long t[N * 4], mx[N * 4];

void upd(int pos, int val, int v = 1, int tl = 1, int tr = n){
      if(tl == tr){
            t[v] = val;
            mx[v] = val;
      } else {
            int tm = (tl + tr) >> 1;
            if(pos <= tm)
                  upd(pos, val, v << 1, tl, tm);
            else
                  upd(pos, val, v << 1 | 1, tm + 1, tr);
            t[v] = t[v << 1] + t[v << 1 | 1];
            mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
      }
}

void upd1(int l, int r, int v = 1, int tl = 1, int tr = n){
      if(l > tr || tl > r || mx[v] < 1)
            return ;
      if(tl == tr){
            t[v] = t[v] / k;
            mx[v] = t[v];
            return ;
      }
      int tm = (tl + tr) >> 1;
      upd1(l, r, v << 1, tl, tm);
      upd1(l, r, v << 1 | 1, tm + 1, tr);
      t[v] = t[v << 1] + t[v << 1 | 1];
      mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
}

long long get(int l, int r, int v = 1, int tl = 1, int tr = n){
      if(l > tr || tl > r)
            return 0;
      if(l <= tl && tr <= r)
            return t[v];
      int tm = (tl + tr) >> 1;
      return get(l, r, v << 1, tl, tm) +
                  get(l, r, v << 1 | 1, tm + 1, tr);
}

int main(){
      cin >> n >> q >> k;

      for(int i = 1; i <= n; i ++){
            scanf("%d", a+i);
            upd(i, a[i]);
      }

      while(q --){
            int tp, l, r;
            scanf("%d %d %d", &tp, &l, &r);
            if(tp == 1)
                  upd(l, r);
            if(tp == 2 && k > 1)
                  upd1(l, r);
            if(tp == 3)
                  printf("%lld\n", get(l, r));
      }
}

Compilation message (stderr)

sterilizing.cpp: In function 'int main()':
sterilizing.cpp:54:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", a+i);
             ~~~~~^~~~~~~~~~~
sterilizing.cpp:60:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d %d", &tp, &l, &r);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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