oj.uz

Submission #42669

# Submission time Handle Problem Language Result Execution time Memory
42669 2018-03-02T01:24:56 Z funcsr Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 ms 37088 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) {
      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 34 ms 2576 KB Output is correct
3 Correct 12 ms 2576 KB Output is correct
4 Correct 44 ms 2676 KB Output is correct
5 Correct 41 ms 2832 KB Output is correct
6 Correct 30 ms 3044 KB Output is correct
7 Correct 38 ms 3212 KB Output is correct
8 Correct 38 ms 3272 KB Output is correct
9 Correct 50 ms 3388 KB Output is correct
10 Correct 43 ms 3468 KB Output is correct
11 Correct 34 ms 3496 KB Output is correct
12 Correct 39 ms 3568 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 5096 KB Output is correct
2 Correct 70 ms 5732 KB Output is correct
3 Correct 91 ms 6136 KB Output is correct
4 Correct 214 ms 7040 KB Output is correct
5 Correct 295 ms 9672 KB Output is correct
6 Correct 294 ms 11080 KB Output is correct
7 Execution timed out 5100 ms 11352 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 620 ms 12396 KB Output is correct
2 Correct 668 ms 14136 KB Output is correct
3 Correct 1275 ms 15192 KB Output is correct
4 Correct 901 ms 16852 KB Output is correct
5 Correct 1076 ms 20388 KB Output is correct
6 Correct 1303 ms 22788 KB Output is correct
7 Correct 1002 ms 25272 KB Output is correct
8 Correct 1806 ms 27720 KB Output is correct
9 Correct 1371 ms 30172 KB Output is correct
10 Correct 1738 ms 32360 KB Output is correct
11 Correct 1143 ms 34816 KB Output is correct
12 Correct 2503 ms 37088 KB Output is correct