oj.uz

Submission #42670

# Submission time Handle Problem Language Result Execution time Memory
42670 2018-03-02T01:25:35 Z funcsr Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 2661 ms 38096 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cassert>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define MAX_N (1<<17)
#define _1 first
#define _2 second
P seg[MAX_N*2-1] = {};
long long sum[MAX_N*2-1] = {};
void update(int k, int v) {
  k += MAX_N-1;
  seg[k] = P(v, k-(MAX_N-1));
  sum[k] = v;
  while (k > 0) {
    k = (k-1) / 2;
    seg[k] = max(seg[k*2+1], seg[k*2+2]);
    sum[k] = sum[k*2+1] + sum[k*2+2];
  }
}
P query_max(int a, int b, int k=0, int l=0, int r=MAX_N) {
  if (b <= l || r <= a) return P(-1, -1);
  if (a <= l && r <= b) return seg[k];
  return max(query_max(a, b, k*2+1, l, (l+r)/2), query_max(a, b, k*2+2, (l+r)/2, r));
}
long long query_sum(int a, int b, int k=0, int l=0, int r=MAX_N) {
  if (b <= l || r <= a) return 0;
  if (a <= l && r <= b) return sum[k];
  return query_sum(a, b, k*2+1, l, (l+r)/2) + query_sum(a, b, k*2+2, (l+r)/2, r);
}

int N, Q, K;

int main() {
  cin >> N >> Q >> K;
  rep(i, N) {
    int a;
    cin >> a;
    update(i, a);
  }
  rep(i, Q) {
    int t, l, r;
    cin >> t >> l >> r;
    l--, r--;
    if (t == 1) {
      r++;
      update(l, r);
    }
    else if (t == 2) {
      if (K == 1) continue;
      queue<P> qs;
      qs.push(P(l, r+1));
      while (!qs.empty()) {
        int l = qs.front()._1, r = qs.front()._2; qs.pop();
        P p = query_max(l, r);
        int val = p._1, pos = p._2;
        if (val <= 0) continue;
        update(pos, val/K);
        if (l < pos) qs.push(P(l, pos));
        if (pos+1 < r) qs.push(P(pos+1, r));
      }
    }
    else {
      cout << query_sum(l, r+1) << "\n";
    }
  }
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2424 KB Output is correct
2 Correct 5 ms 2528 KB Output is correct
3 Correct 12 ms 2596 KB Output is correct
4 Correct 48 ms 2796 KB Output is correct
5 Correct 40 ms 2796 KB Output is correct
6 Correct 29 ms 2796 KB Output is correct
7 Correct 40 ms 2800 KB Output is correct
8 Correct 37 ms 2800 KB Output is correct
9 Correct 48 ms 2800 KB Output is correct
10 Correct 34 ms 2800 KB Output is correct
11 Correct 35 ms 2828 KB Output is correct
12 Correct 37 ms 2828 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 5216 KB Output is correct
2 Correct 163 ms 6428 KB Output is correct
3 Correct 149 ms 8684 KB Output is correct
4 Correct 198 ms 11268 KB Output is correct
5 Correct 230 ms 13800 KB Output is correct
6 Correct 226 ms 16300 KB Output is correct
7 Correct 233 ms 18856 KB Output is correct
8 Correct 226 ms 21324 KB Output is correct
9 Correct 222 ms 23520 KB Output is correct
10 Correct 213 ms 25748 KB Output is correct
11 Correct 225 ms 28248 KB Output is correct
12 Correct 225 ms 30452 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 30452 KB Output is correct
2 Correct 66 ms 30452 KB Output is correct
3 Correct 86 ms 30452 KB Output is correct
4 Correct 212 ms 30452 KB Output is correct
5 Correct 284 ms 30452 KB Output is correct
6 Correct 276 ms 30452 KB Output is correct
7 Correct 201 ms 31288 KB Output is correct
8 Correct 278 ms 32560 KB Output is correct
9 Correct 267 ms 33728 KB Output is correct
10 Correct 279 ms 35304 KB Output is correct
11 Correct 282 ms 36400 KB Output is correct
12 Correct 262 ms 37688 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 683 ms 37688 KB Output is correct
2 Correct 665 ms 37688 KB Output is correct
3 Correct 1242 ms 37688 KB Output is correct
4 Correct 926 ms 37688 KB Output is correct
5 Correct 1088 ms 37936 KB Output is correct
6 Correct 1367 ms 38096 KB Output is correct
7 Correct 1026 ms 38096 KB Output is correct
8 Correct 1842 ms 38096 KB Output is correct
9 Correct 1457 ms 38096 KB Output is correct
10 Correct 1785 ms 38096 KB Output is correct
11 Correct 1120 ms 38096 KB Output is correct
12 Correct 2661 ms 38096 KB Output is correct