oj.uz

Submission #234079

# Submission time Handle Problem Language Result Execution time Memory
234079 2020-05-22T23:44:16 Z caoash Wall (IOI14_wall) C++14
100 / 100
 1251 ms 99596 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 37 ms 62976 KB Output is correct
2 Correct 37 ms 63096 KB Output is correct
3 Correct 38 ms 62968 KB Output is correct
4 Correct 42 ms 63228 KB Output is correct
5 Correct 45 ms 63224 KB Output is correct
6 Correct 42 ms 63224 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 62968 KB Output is correct
2 Correct 205 ms 76640 KB Output is correct
3 Correct 227 ms 70136 KB Output is correct
4 Correct 556 ms 81144 KB Output is correct
5 Correct 383 ms 82044 KB Output is correct
6 Correct 374 ms 80532 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 62976 KB Output is correct
2 Correct 37 ms 63104 KB Output is correct
3 Correct 36 ms 62968 KB Output is correct
4 Correct 41 ms 63224 KB Output is correct
5 Correct 42 ms 63224 KB Output is correct
6 Correct 43 ms 63224 KB Output is correct
7 Correct 36 ms 62968 KB Output is correct
8 Correct 204 ms 76664 KB Output is correct
9 Correct 220 ms 70136 KB Output is correct
10 Correct 561 ms 81016 KB Output is correct
11 Correct 381 ms 82020 KB Output is correct
12 Correct 373 ms 80504 KB Output is correct
13 Correct 35 ms 62968 KB Output is correct
14 Correct 201 ms 76536 KB Output is correct
15 Correct 69 ms 64248 KB Output is correct
16 Correct 567 ms 81300 KB Output is correct
17 Correct 381 ms 80764 KB Output is correct
18 Correct 378 ms 80632 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 62964 KB Output is correct
2 Correct 36 ms 63096 KB Output is correct
3 Correct 37 ms 62968 KB Output is correct
4 Correct 41 ms 63224 KB Output is correct
5 Correct 41 ms 63224 KB Output is correct
6 Correct 41 ms 63232 KB Output is correct
7 Correct 34 ms 62976 KB Output is correct
8 Correct 206 ms 76536 KB Output is correct
9 Correct 226 ms 70136 KB Output is correct
10 Correct 563 ms 81016 KB Output is correct
11 Correct 381 ms 82040 KB Output is correct
12 Correct 370 ms 80504 KB Output is correct
13 Correct 35 ms 62968 KB Output is correct
14 Correct 211 ms 76536 KB Output is correct
15 Correct 69 ms 64120 KB Output is correct
16 Correct 565 ms 81292 KB Output is correct
17 Correct 382 ms 80760 KB Output is correct
18 Correct 387 ms 80632 KB Output is correct
19 Correct 1251 ms 99404 KB Output is correct
20 Correct 1237 ms 97032 KB Output is correct
21 Correct 1222 ms 99556 KB Output is correct
22 Correct 1213 ms 97144 KB Output is correct
23 Correct 1208 ms 96888 KB Output is correct
24 Correct 1218 ms 96888 KB Output is correct
25 Correct 1213 ms 96888 KB Output is correct
26 Correct 1218 ms 99596 KB Output is correct
27 Correct 1251 ms 99448 KB Output is correct
28 Correct 1219 ms 96888 KB Output is correct
29 Correct 1230 ms 97052 KB Output is correct
30 Correct 1251 ms 96868 KB Output is correct