oj.uz

Submission #128065

# Submission time Handle Problem Language Result Execution time Memory
128065 2019-07-10T11:40:29 Z mirbek01 Sterilizing Spray (JOI15_sterilizing) C++11
100 / 100
 336 ms 7816 KB 
# 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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 7 ms 632 KB Output is correct
6 Correct 6 ms 632 KB Output is correct
7 Correct 7 ms 504 KB Output is correct
8 Correct 7 ms 632 KB Output is correct
9 Correct 8 ms 632 KB Output is correct
10 Correct 7 ms 504 KB Output is correct
11 Correct 7 ms 632 KB Output is correct
12 Correct 7 ms 632 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 5112 KB Output is correct
2 Correct 67 ms 4572 KB Output is correct
3 Correct 72 ms 6624 KB Output is correct
4 Correct 91 ms 7260 KB Output is correct
5 Correct 106 ms 7816 KB Output is correct
6 Correct 104 ms 7684 KB Output is correct
7 Correct 108 ms 7744 KB Output is correct
8 Correct 106 ms 7800 KB Output is correct
9 Correct 95 ms 7644 KB Output is correct
10 Correct 102 ms 7556 KB Output is correct
11 Correct 96 ms 7672 KB Output is correct
12 Correct 95 ms 7660 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1144 KB Output is correct
2 Correct 23 ms 2808 KB Output is correct
3 Correct 29 ms 2936 KB Output is correct
4 Correct 66 ms 2808 KB Output is correct
5 Correct 99 ms 6396 KB Output is correct
6 Correct 100 ms 6264 KB Output is correct
7 Correct 90 ms 6392 KB Output is correct
8 Correct 98 ms 6400 KB Output is correct
9 Correct 89 ms 6136 KB Output is correct
10 Correct 88 ms 6108 KB Output is correct
11 Correct 89 ms 6136 KB Output is correct
12 Correct 89 ms 6264 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 4420 KB Output is correct
2 Correct 127 ms 4472 KB Output is correct
3 Correct 150 ms 3832 KB Output is correct
4 Correct 164 ms 3448 KB Output is correct
5 Correct 195 ms 7676 KB Output is correct
6 Correct 234 ms 7576 KB Output is correct
7 Correct 188 ms 7564 KB Output is correct
8 Correct 271 ms 7648 KB Output is correct
9 Correct 225 ms 7416 KB Output is correct
10 Correct 254 ms 7552 KB Output is correct
11 Correct 194 ms 7416 KB Output is correct
12 Correct 336 ms 7444 KB Output is correct