oj.uz

답안 #1103977

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1103977 2024-10-22T13:52:54 Z Naxocist 벽 (IOI14_wall) C++17
100 / 100
 1082 ms 126004 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

#define INF 2e9
const int N = 2e6 + 3;
struct node {
  int val, lzmn, lzmx;
  node(): val(0), lzmn(INF), lzmx(-INF) {}
} seg[4*N];

int n;

void push(int i, int l, int r) {
  seg[i].val = min(seg[i].val, seg[i].lzmn);
  seg[i].val = max(seg[i].val, seg[i].lzmx);

  int mn = seg[i].lzmn, mx = seg[i].lzmx;

  if(l != r) {
    seg[2*i].lzmn = min(seg[2*i].lzmn, mn);
    seg[2*i+1].lzmn = min(seg[2*i+1].lzmn, mn);
    seg[2*i].lzmn = max(seg[2*i].lzmn, mx);
    seg[2*i+1].lzmn = max(seg[2*i+1].lzmn, mx);

    seg[2*i].lzmx = max(seg[2*i].lzmx, mx);
    seg[2*i+1].lzmx = max(seg[2*i+1].lzmx, mx);
    seg[2*i].lzmx = min(seg[2*i].lzmx, mn);
    seg[2*i+1].lzmx = min(seg[2*i+1].lzmx, mn);
  }

  seg[i].lzmn = INF, seg[i].lzmx = -INF;
}

void upd(int a, int b, int mn, int mx, int i = 1, int l = 1, int r = n) {
  push(i,l,r);
  if(a <= l and r <= b) {
    seg[i].lzmx = mx;
    seg[i].lzmn = mn;
    push(i,l,r);
    return ;
  }
  if(r < a or l > b) return ;
  int md = l + (r-l)/2;
  upd(a,b,mn,mx,2*i,l,md); upd(a,b,mn,mx,2*i+1,md+1,r);
}

int qry(int p, int i = 1, int l = 1, int r = n) {
  push(i,l,r);
  if(l == r) return seg[i].val;
  int md = l + (r-l)/2;
  if(p <= md) return qry(p,2*i,l,md);
  return qry(p,2*i+1,md+1,r);
}

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) {
    int l = left[i], r = right[i], o = op[i], h = height[i]; l++, r++;
    int mn, mx;
    if(o == 1) upd(l,r,INF,h); // add
    else upd(l,r,h,-INF); // rem
  }

  for(int i=0; i<n; ++i) {
    finalHeight[i] = qry(i+1);
  }
  return;
}

Compilation message

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:61:9: warning: unused variable 'mn' [-Wunused-variable]
   61 |     int mn, mx;
      |         ^~
wall.cpp:61:13: warning: unused variable 'mx' [-Wunused-variable]
   61 |     int mn, mx;
      |             ^~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 94164 KB Output is correct
2 Correct 52 ms 94328 KB Output is correct
3 Correct 48 ms 94280 KB Output is correct
4 Correct 37 ms 94280 KB Output is correct
5 Correct 50 ms 94536 KB Output is correct
6 Correct 32 ms 94564 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 94288 KB Output is correct
2 Correct 113 ms 101960 KB Output is correct
3 Correct 220 ms 101264 KB Output is correct
4 Correct 477 ms 102728 KB Output is correct
5 Correct 311 ms 108616 KB Output is correct
6 Correct 318 ms 111180 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 94288 KB Output is correct
2 Correct 16 ms 94428 KB Output is correct
3 Correct 42 ms 94320 KB Output is correct
4 Correct 32 ms 94584 KB Output is correct
5 Correct 37 ms 94432 KB Output is correct
6 Correct 36 ms 94280 KB Output is correct
7 Correct 25 ms 94248 KB Output is correct
8 Correct 123 ms 101960 KB Output is correct
9 Correct 175 ms 100680 KB Output is correct
10 Correct 540 ms 102728 KB Output is correct
11 Correct 314 ms 103228 KB Output is correct
12 Correct 322 ms 111164 KB Output is correct
13 Correct 26 ms 94280 KB Output is correct
14 Correct 104 ms 107336 KB Output is correct
15 Correct 65 ms 95492 KB Output is correct
16 Correct 542 ms 102976 KB Output is correct
17 Correct 308 ms 107760 KB Output is correct
18 Correct 306 ms 111432 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 94288 KB Output is correct
2 Correct 27 ms 94292 KB Output is correct
3 Correct 24 ms 94280 KB Output is correct
4 Correct 34 ms 94544 KB Output is correct
5 Correct 32 ms 94280 KB Output is correct
6 Correct 34 ms 94536 KB Output is correct
7 Correct 14 ms 94336 KB Output is correct
8 Correct 118 ms 101960 KB Output is correct
9 Correct 223 ms 101204 KB Output is correct
10 Correct 481 ms 109896 KB Output is correct
11 Correct 295 ms 103212 KB Output is correct
12 Correct 280 ms 103256 KB Output is correct
13 Correct 19 ms 94384 KB Output is correct
14 Correct 104 ms 107336 KB Output is correct
15 Correct 41 ms 95424 KB Output is correct
16 Correct 507 ms 108100 KB Output is correct
17 Correct 300 ms 107852 KB Output is correct
18 Correct 301 ms 102984 KB Output is correct
19 Correct 1074 ms 120132 KB Output is correct
20 Correct 1069 ms 117576 KB Output is correct
21 Correct 1082 ms 125244 KB Output is correct
22 Correct 986 ms 126004 KB Output is correct
23 Correct 976 ms 118004 KB Output is correct
24 Correct 1004 ms 123100 KB Output is correct
25 Correct 1061 ms 122940 KB Output is correct
26 Correct 1060 ms 120200 KB Output is correct
27 Correct 1066 ms 120356 KB Output is correct
28 Correct 1048 ms 117576 KB Output is correct
29 Correct 999 ms 117824 KB Output is correct
30 Correct 967 ms 117832 KB Output is correct