oj.uz

Submission #106316

# Submission time Handle Problem Language Result Execution time Memory
106316 2019-04-17T21:06:24 Z xiaowuc1 Watering can (POI13_kon) C++14
100 / 100
 355 ms 27428 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] + ragetreelazy[2*idx], ragetreemin[2*idx+1] + ragetreelazy[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] = 1;
    ragetreemin[idx] = 1e9;
    return;
  }
  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;
}

int k;
void ragetreeinit(int idx, int lhs, int rhs, int *D) {
  if(lhs == rhs) {
    if(D[lhs] >= k) {
      ragetreesum[idx] = 1;
      ragetreemin[idx] = 1e9;
    }
    else {
      ragetreemin[idx] = k - 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 kk, int *D) {
  n = nn;
  k = kk;
  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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 5 ms 588 KB Output is correct
3 Correct 2 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 1460 KB Output is correct
2 Correct 49 ms 2808 KB Output is correct
3 Correct 37 ms 2808 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 2296 KB Output is correct
2 Correct 63 ms 2168 KB Output is correct
3 Correct 53 ms 4472 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 4088 KB Output is correct
2 Correct 93 ms 7096 KB Output is correct
3 Correct 113 ms 5916 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 4688 KB Output is correct
2 Correct 200 ms 9132 KB Output is correct
3 Correct 154 ms 9724 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 4828 KB Output is correct
2 Correct 194 ms 12792 KB Output is correct
3 Correct 211 ms 10972 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 8428 KB Output is correct
2 Correct 307 ms 15716 KB Output is correct
3 Correct 295 ms 18688 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 15228 KB Output is correct
2 Correct 355 ms 25868 KB Output is correct
3 Correct 334 ms 24776 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 15256 KB Output is correct
2 Correct 349 ms 27428 KB Output is correct
3 Correct 331 ms 25080 KB Output is correct