oj.uz

답안 #50262

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
50262 2018-06-08T17:13:48 Z mirbek01 벽 (IOI14_wall) C++17
100 / 100
 1304 ms 89140 KB 
#include "wall.h"

# include <bits/stdc++.h>

using namespace std;

const int N = 2e6 + 2;

struct st{
      int mn, mx;
      st(){
            mx = 0;
            mn = 1e5 + 1;
      }
}t[N * 4];

int n;

void upd(int v, int x, int tp){
      if(tp == 1){
            t[v].mx = max(t[v].mx, x);
            t[v].mn = max(t[v].mn, x);
      } else {
            t[v].mn = min(t[v].mn, x);
            t[v].mx = min(t[v].mx, x);
      }
}

void down(int v){
      upd(v << 1, t[v].mx, 1);
      upd(v << 1, t[v].mn, 2);
      upd((v << 1) | 1, t[v].mx, 1);
      upd((v << 1) | 1, t[v].mn, 2);
      t[v].mx = 0;
      t[v].mn = 1e5 + 1;
}

void update(int l, int r, int x, int tp, int v = 1, int tl = 1, int tr = n){
      if(l <= tl && tr <= r){
            upd(v, x, tp);
            return ;
      }
      if(tl > r || l > tr) return ;
      down(v);
      int tm = (tl + tr) >> 1;
      update(l, r, x, tp, v << 1, tl, tm);
      update(l, r, x, tp, (v << 1) | 1, tm + 1, tr);
}

int get(int pos, int v = 1, int tl = 1, int tr = n){
      if(tl == tr){
            return t[v].mx;
      }
      down(v);
      int tm = (tl + tr) >> 1;
      if(pos <= tm)
            return get(pos, v << 1, tl, tm);
      return get(pos, (v << 1) | 1, tm + 1, tr);
}

void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
      n = N;
      for(int i = 0; i < k; i ++){
            update(left[i] + 1, right[i] + 1, height[i], op[i]);
      }
      for(int i = 0; i < n; i ++){
            finalHeight[i] = get(i + 1);
      }
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 62968 KB Output is correct
2 Correct 69 ms 63164 KB Output is correct
3 Correct 51 ms 63164 KB Output is correct
4 Correct 61 ms 63164 KB Output is correct
5 Correct 51 ms 63164 KB Output is correct
6 Correct 52 ms 63196 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 63196 KB Output is correct
2 Correct 230 ms 70968 KB Output is correct
3 Correct 260 ms 70968 KB Output is correct
4 Correct 709 ms 71540 KB Output is correct
5 Correct 425 ms 72116 KB Output is correct
6 Correct 426 ms 72116 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 72116 KB Output is correct
2 Correct 49 ms 72116 KB Output is correct
3 Correct 54 ms 72116 KB Output is correct
4 Correct 54 ms 72116 KB Output is correct
5 Correct 54 ms 72116 KB Output is correct
6 Correct 57 ms 72116 KB Output is correct
7 Correct 50 ms 72116 KB Output is correct
8 Correct 241 ms 72116 KB Output is correct
9 Correct 298 ms 72116 KB Output is correct
10 Correct 684 ms 72116 KB Output is correct
11 Correct 437 ms 72196 KB Output is correct
12 Correct 391 ms 72212 KB Output is correct
13 Correct 49 ms 72212 KB Output is correct
14 Correct 223 ms 72212 KB Output is correct
15 Correct 86 ms 72212 KB Output is correct
16 Correct 712 ms 72212 KB Output is correct
17 Correct 409 ms 72212 KB Output is correct
18 Correct 403 ms 72212 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 72212 KB Output is correct
2 Correct 50 ms 72212 KB Output is correct
3 Correct 55 ms 72212 KB Output is correct
4 Correct 73 ms 72212 KB Output is correct
5 Correct 65 ms 72212 KB Output is correct
6 Correct 54 ms 72212 KB Output is correct
7 Correct 55 ms 72212 KB Output is correct
8 Correct 214 ms 72212 KB Output is correct
9 Correct 256 ms 72212 KB Output is correct
10 Correct 751 ms 72212 KB Output is correct
11 Correct 581 ms 72212 KB Output is correct
12 Correct 448 ms 72232 KB Output is correct
13 Correct 48 ms 72232 KB Output is correct
14 Correct 245 ms 72232 KB Output is correct
15 Correct 82 ms 72232 KB Output is correct
16 Correct 689 ms 72232 KB Output is correct
17 Correct 500 ms 72232 KB Output is correct
18 Correct 412 ms 72232 KB Output is correct
19 Correct 1289 ms 89088 KB Output is correct
20 Correct 1239 ms 89088 KB Output is correct
21 Correct 1148 ms 89088 KB Output is correct
22 Correct 1075 ms 89088 KB Output is correct
23 Correct 1134 ms 89088 KB Output is correct
24 Correct 1201 ms 89088 KB Output is correct
25 Correct 1264 ms 89088 KB Output is correct
26 Correct 1304 ms 89088 KB Output is correct
27 Correct 1227 ms 89140 KB Output is correct
28 Correct 1201 ms 89140 KB Output is correct
29 Correct 1216 ms 89140 KB Output is correct
30 Correct 1177 ms 89140 KB Output is correct