oj.uz

Submission #229501

# Submission time Handle Problem Language Result Execution time Memory
229501 2020-05-04T20:11:50 Z tushar_2658 Wall (IOI14_wall) C++14
100 / 100
 1255 ms 99704 KB 
#include "wall.h"
#include "bits/stdc++.h"
using namespace std;

const int maxn = 2000005;
int N, K;
int mn[maxn << 2], mx[maxn << 2], t[maxn << 2];

void applymn(int node, int h){
  mn[node] = min(mn[node], h); 
  mx[node] = min(mx[node], mn[node]);
}

void applymx(int node, int h){
  mx[node] = max(mx[node], h);
  mn[node] = max(mn[node], mx[node]);
}

void push_down(int node){
  applymn(2*node, mn[node]); 
  applymn(2*node + 1, mn[node]);
  applymx(2*node, mx[node]);
  applymx(2*node + 1, mx[node]);
  mn[node] = INT_MAX;
  mx[node] = 0;
}

void upd(int node, int b, int e, int i, int j, int val, int id){
  if(i > e || j < b)return;
  if(b >= i && j >= e){
    if(id == 1){
      applymx(node, val);
    }else {
      applymn(node, val);
    }
    return;
  }
  push_down(node);
  int mid = (b + e) >> 1;
  upd(2*node, b, mid, i, j, val, id);
  upd(2*node + 1, mid + 1, e, i, j, val, id);
}

int query(int node, int b, int e, int i){
  if(b == e){
    return min(max(0, mn[node]), mx[node]);
  }else {
    push_down(node);
    int mid = (b + e) >> 1;
    if(i <= mid){
      return query(2*node, b, mid, i);
    }else {
      return query(2*node + 1, mid + 1, e, i);
    }
  }
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  N = n, K = k;
  for(int i = 0; i < (maxn << 2); ++i){
    mn[i] = INT_MAX;
    mx[i] = 0;
  }
  for(int i = 0; i < K; ++i){
    upd(1, 1, N, left[i] + 1, right[i] + 1, height[i], op[i]);
  }
  for(int i = 1; i <= N; ++i){
    finalHeight[i - 1] = query(1, 1, N, i);
  }

  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 62968 KB Output is correct
2 Correct 40 ms 63104 KB Output is correct
3 Correct 38 ms 62976 KB Output is correct
4 Correct 47 ms 63096 KB Output is correct
5 Correct 43 ms 63224 KB Output is correct
6 Correct 44 ms 63148 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 62976 KB Output is correct
2 Correct 202 ms 71672 KB Output is correct
3 Correct 226 ms 67320 KB Output is correct
4 Correct 564 ms 72568 KB Output is correct
5 Correct 390 ms 73080 KB Output is correct
6 Correct 369 ms 73184 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 62976 KB Output is correct
2 Correct 39 ms 63096 KB Output is correct
3 Correct 38 ms 62968 KB Output is correct
4 Correct 44 ms 63232 KB Output is correct
5 Correct 43 ms 63224 KB Output is correct
6 Correct 45 ms 63224 KB Output is correct
7 Correct 40 ms 62968 KB Output is correct
8 Correct 209 ms 76536 KB Output is correct
9 Correct 222 ms 70140 KB Output is correct
10 Correct 576 ms 81016 KB Output is correct
11 Correct 377 ms 82040 KB Output is correct
12 Correct 366 ms 80504 KB Output is correct
13 Correct 36 ms 62972 KB Output is correct
14 Correct 214 ms 76664 KB Output is correct
15 Correct 69 ms 64120 KB Output is correct
16 Correct 573 ms 81312 KB Output is correct
17 Correct 387 ms 80632 KB Output is correct
18 Correct 381 ms 80632 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 62976 KB Output is correct
2 Correct 39 ms 63096 KB Output is correct
3 Correct 38 ms 62968 KB Output is correct
4 Correct 44 ms 63228 KB Output is correct
5 Correct 43 ms 63224 KB Output is correct
6 Correct 45 ms 63224 KB Output is correct
7 Correct 38 ms 63096 KB Output is correct
8 Correct 208 ms 76664 KB Output is correct
9 Correct 223 ms 70136 KB Output is correct
10 Correct 591 ms 80952 KB Output is correct
11 Correct 392 ms 82040 KB Output is correct
12 Correct 383 ms 80504 KB Output is correct
13 Correct 37 ms 62968 KB Output is correct
14 Correct 210 ms 76596 KB Output is correct
15 Correct 71 ms 64120 KB Output is correct
16 Correct 572 ms 81212 KB Output is correct
17 Correct 388 ms 80888 KB Output is correct
18 Correct 369 ms 80632 KB Output is correct
19 Correct 1255 ms 99704 KB Output is correct
20 Correct 1248 ms 96968 KB Output is correct
21 Correct 1244 ms 99320 KB Output is correct
22 Correct 1231 ms 96888 KB Output is correct
23 Correct 1232 ms 96960 KB Output is correct
24 Correct 1234 ms 97144 KB Output is correct
25 Correct 1225 ms 96888 KB Output is correct
26 Correct 1216 ms 99444 KB Output is correct
27 Correct 1221 ms 99576 KB Output is correct
28 Correct 1202 ms 97016 KB Output is correct
29 Correct 1251 ms 96892 KB Output is correct
30 Correct 1213 ms 96808 KB Output is correct