답안 #42667

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
42667 2018-03-02T01:22:59 Z funcsr Sterilizing Spray (JOI15_sterilizing) C++14
컴파일 오류
0 ms 0 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
struct SegTree {
  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 A[100000];
SegTree seg;

int main() {
  cin >> N >> Q >> K;
  rep(i, N) cin >> A[i];
  rep(i, N) seg.update(i, A[i]);
  rep(i, Q) {
    int t, l, r;
    cin >> t >> l >> r;
    l--, r--;
    if (t == 1) {
      r++;
      seg.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 = seg.query_max(l, r);
        int val = p._1, pos = p._2;
        if (val <= 0) continue;
        seg.update(pos, val/K);
        if (l < pos) qs.push(P(l, pos));
        if (pos+1 < r) qs.push(P(pos+1, r));
      }
    }
    else {
      cout << seg.query_sum(l, r+1) << "\n";
    }
  }
  return 0;
}

Compilation message

Compilation timeout while compiling sterilizing