oj.uz

답안 #106311

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
106311 2019-04-17T20:59:47 Z xiaowuc1 Watering can (POI13_kon) C++14
0 / 100
 129 ms 31896 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_RAGETREE_SZ = 300005;

int ragetreesum[4 * MAX_RAGETREE_SZ];
int ragetreemin[4 * MAX_RAGETREE_SZ];
int ragetreelazy[4 * MAX_RAGETREE_SZ];
int n;

void pushdown(int idx) {
  ragetreelazy[2*idx] += ragetreelazy[idx];
  ragetreelazy[2*idx+1] += ragetreelazy[idx];
  ragetreelazy[idx] = 0;
}
void pullup(int idx) {
  ragetreesum[idx] = ragetreesum[2*idx] + ragetreesum[2*idx+1];
  ragetreemin[idx] = min(ragetreemin[2*idx], ragetreemin[2*idx+1]);
}
void ragetreedec(int idx, int lhs, int rhs, int l, int r) {
  if(lhs >= l && rhs <= r && ragetreemin[idx] + ragetreelazy[idx] - 1 > 0) {
    ragetreelazy[idx]--;
    return;
  }
  if(lhs == rhs) {
    ragetreesum[idx]++;
    ragetreemin[idx] = 1e9;
  }
  pushdown(idx);
  int mid = (lhs+rhs)/2;
  if(mid >= l) ragetreedec(2*idx, lhs, mid, l, r);
  if(mid+1 <= r) ragetreedec(2*idx+1, mid+1, rhs, l, r);
  pullup(idx);
}
int ragetreequery(int idx, int lhs, int rhs, int l, int r) {
  if(lhs >= l && rhs <= r) return ragetreesum[idx];
  int ret = 0;
  int mid = (lhs+rhs)/2;
  if(mid >= l) ret += ragetreequery(2*idx, lhs, mid, l, r);
  if(mid+1 <= r) ret += ragetreequery(2*idx+1, mid+1, rhs, l, r);
  return ret;
}

void ragetreeinit(int idx, int lhs, int rhs, int *D) {
  if(lhs == rhs) {
    if(D[lhs] <= 0) {
      ragetreesum[idx] = 1;
      ragetreemin[idx] = 1e9;
    }
    else {
      ragetreemin[idx] = D[lhs];
    }
    return;
  }
  int mid = (lhs+rhs)/2;
  ragetreeinit(2*idx, lhs, mid, D);
  ragetreeinit(2*idx+1, mid+1, rhs, D);
  pullup(idx);
}

void inicjuj(int nn, int k, int *D) {
  n = nn;
  for(int i = 0; i < n; i++) D[i] = k - D[i];
  ragetreeinit(1, 0, n-1, D);
}

// inc [a, b] by 1
void podlej(int a, int b) {
  ragetreedec(1, 0, n-1, a, b);
}
// count
int dojrzale(int a, int b) {
  return ragetreequery(1, 0, n-1, a, b);
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 27 ms 3172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 4472 KB Output is correct
2 Incorrect 66 ms 4552 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 22 ms 7160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 30 ms 7288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 31 ms 8960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 65 ms 16256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 129 ms 31896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 80 ms 27836 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -