Submission #42670

#	Time	Username	Problem	Language	Result	Execution time	Memory
42670		funcsr	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	2661 ms	38096 KiB

sterilizing

#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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75