oj.uz

Submission #713026

# Submission time Handle Problem Language Result Execution time Memory
713026 2023-03-20T22:35:51 Z garyye Wall (IOI14_wall) C++14
100 / 100
 1262 ms 84504 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
#define fi first
#define se second

const int ADD = 1;
const int DEL = 2;
const int N = 2e6 + 5;
const int INF = 1e9+10;

int mn[N * 4], mx[N * 4];
int* H;

// i <= j 
int clamp(int x, int i, int j) {
  return min(max(x, i), j);
}

void pull(int u) {
  int p = u >> 1;
  mx[u] = clamp(mx[u], mn[p], mx[p]);
  mn[u] = clamp(mn[u], mn[p], mx[p]);
}

void update(int u, int L, int R, int i, int j, int op, int x) {
  if(j < L || R < i) {
    return;
  }

  if(i <= L && R <= j) {
    if(op == ADD) {
      mn[u] = max(mn[u], x);
      mx[u] = max(mx[u], mn[u]);
    } else {
      mx[u] = min(mx[u], x);
      mn[u] = min(mn[u], mx[u]);
    }
    if(L == R) {
      H[L] = clamp(0, mn[u], mx[u]);
    }
  } else {
    int mid = (L + R) >> 1;

    pull(u * 2);
    pull(u * 2 + 1);
    mn[u] = 0, mx[u] = INF;

    update(u * 2, L, mid, i, j, op, x);
    update(u * 2 + 1, mid + 1, R, i, j, op, x);
  }
}



void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  fill(mx, mx + N * 4, 1e9 + 10);
  H = finalHeight;
  for(int i = 0; i < k; ++i) {
    update(1, 0, n - 1, left[i], right[i], op[i], height[i]);
  }
  for(int i = 0; i < n; ++i) {
    update(1, 0, n - 1, i, i, ADD, 0);
  }

}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31564 KB Output is correct
2 Correct 18 ms 31680 KB Output is correct
3 Correct 15 ms 31656 KB Output is correct
4 Correct 22 ms 31956 KB Output is correct
5 Correct 23 ms 31984 KB Output is correct
6 Correct 29 ms 31936 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 31572 KB Output is correct
2 Correct 157 ms 42656 KB Output is correct
3 Correct 163 ms 38476 KB Output is correct
4 Correct 441 ms 44264 KB Output is correct
5 Correct 304 ms 44716 KB Output is correct
6 Correct 304 ms 44776 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31820 KB Output is correct
2 Correct 20 ms 31700 KB Output is correct
3 Correct 17 ms 31572 KB Output is correct
4 Correct 22 ms 31912 KB Output is correct
5 Correct 21 ms 31944 KB Output is correct
6 Correct 23 ms 31932 KB Output is correct
7 Correct 17 ms 31512 KB Output is correct
8 Correct 150 ms 42700 KB Output is correct
9 Correct 170 ms 38572 KB Output is correct
10 Correct 483 ms 44312 KB Output is correct
11 Correct 315 ms 44900 KB Output is correct
12 Correct 305 ms 44888 KB Output is correct
13 Correct 15 ms 31608 KB Output is correct
14 Correct 150 ms 42612 KB Output is correct
15 Correct 41 ms 32964 KB Output is correct
16 Correct 509 ms 44524 KB Output is correct
17 Correct 294 ms 44452 KB Output is correct
18 Correct 320 ms 44484 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31572 KB Output is correct
2 Correct 17 ms 31692 KB Output is correct
3 Correct 16 ms 31608 KB Output is correct
4 Correct 21 ms 31956 KB Output is correct
5 Correct 23 ms 31996 KB Output is correct
6 Correct 21 ms 31900 KB Output is correct
7 Correct 16 ms 31572 KB Output is correct
8 Correct 152 ms 42484 KB Output is correct
9 Correct 168 ms 38260 KB Output is correct
10 Correct 424 ms 43684 KB Output is correct
11 Correct 324 ms 43932 KB Output is correct
12 Correct 299 ms 43704 KB Output is correct
13 Correct 20 ms 31540 KB Output is correct
14 Correct 175 ms 41424 KB Output is correct
15 Correct 47 ms 33060 KB Output is correct
16 Correct 441 ms 43300 KB Output is correct
17 Correct 311 ms 42956 KB Output is correct
18 Correct 312 ms 42784 KB Output is correct
19 Correct 1167 ms 74212 KB Output is correct
20 Correct 1141 ms 81936 KB Output is correct
21 Correct 1262 ms 84404 KB Output is correct
22 Correct 1212 ms 81932 KB Output is correct
23 Correct 1139 ms 81912 KB Output is correct
24 Correct 1137 ms 81844 KB Output is correct
25 Correct 1132 ms 81888 KB Output is correct
26 Correct 1208 ms 84484 KB Output is correct
27 Correct 1137 ms 84504 KB Output is correct
28 Correct 1119 ms 81824 KB Output is correct
29 Correct 1133 ms 81828 KB Output is correct
30 Correct 1133 ms 81908 KB Output is correct