oj.uz

답안 #260939

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
260939 2020-08-11T08:18:07 Z my99n 벽 (IOI14_wall) C++14
100 / 100
 866 ms 69688 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2000100;

struct A {
  int mn, mx;
} seg[4*MAXN];

int* ans, N;

void tag (int now, int mn, int mx) {
  // cerr << "tag" << now << ' ' << mn << ' ' << mx << endl;
  seg[now].mn = min(mx, max(mn, seg[now].mn));
  seg[now].mx = max(mn, min(mx, seg[now].mx));
}

void push (int now, int l, int r) {
  if (l == r) {
    ans[l] = min(seg[now].mx, max(seg[now].mn, ans[l]));
  }
  else {
    tag(now*2, seg[now].mn, seg[now].mx);
    tag(now*2+1, seg[now].mn, seg[now].mx);
  }
  seg[now].mn = 0;
  seg[now].mx = 1e9;
}

void build (int now = 1, int l = 0, int r = N-1) {
  seg[now].mn = 0;
  seg[now].mx = 1e9;
  if (l == r) return;
  int mid = (l+r)/2;
  build(now*2, l, mid);
  build(now*2+1, mid+1, r);
}

void update (int a, int b, int mn, int mx, int now = 1, int l = 0, int r = N-1) {
  if (r < a or l > b) return;
  if (a <= l and r <= b) return tag(now, mn, mx);
  push(now, l, r);
  int mid = (l+r)/2;
  update(a, b, mn, mx, now*2, l, mid);
  update(a, b, mn, mx, now*2+1, mid+1, r);
}

void dfs (int now = 1, int l = 0, int r = N-1) {
  push(now, l, r);
  if (l == r) return;
  int mid = (l+r)/2;
  dfs(now*2, l, mid);
  dfs(now*2+1, mid+1, r);
}

void buildWall(int n, int k, int op[], int l[], int r[], int h[], int finalHeight[]){
	ans = finalHeight;
	N = n;
	build();
	for(int i = 0; i < k; i++) {
		if(op[i] == 1) update(l[i], r[i], h[i], 1e9);
		else if(op[i] == 2) update(l[i], r[i], 0, h[i]);
	}
	dfs();
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 7 ms 896 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 7 ms 896 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 182 ms 8616 KB Output is correct
3 Correct 213 ms 4732 KB Output is correct
4 Correct 582 ms 11256 KB Output is correct
5 Correct 351 ms 11896 KB Output is correct
6 Correct 374 ms 11896 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 7 ms 768 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 6 ms 768 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 176 ms 8696 KB Output is correct
9 Correct 198 ms 4728 KB Output is correct
10 Correct 574 ms 11408 KB Output is correct
11 Correct 348 ms 12024 KB Output is correct
12 Correct 352 ms 11768 KB Output is correct
13 Correct 0 ms 256 KB Output is correct
14 Correct 180 ms 8696 KB Output is correct
15 Correct 33 ms 2040 KB Output is correct
16 Correct 590 ms 11676 KB Output is correct
17 Correct 342 ms 11512 KB Output is correct
18 Correct 340 ms 11512 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 8 ms 896 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 6 ms 768 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 179 ms 8696 KB Output is correct
9 Correct 201 ms 4728 KB Output is correct
10 Correct 587 ms 11384 KB Output is correct
11 Correct 357 ms 11896 KB Output is correct
12 Correct 388 ms 11896 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 178 ms 8700 KB Output is correct
15 Correct 34 ms 2048 KB Output is correct
16 Correct 569 ms 11640 KB Output is correct
17 Correct 361 ms 11668 KB Output is correct
18 Correct 396 ms 11640 KB Output is correct
19 Correct 818 ms 59616 KB Output is correct
20 Correct 830 ms 67064 KB Output is correct
21 Correct 821 ms 69624 KB Output is correct
22 Correct 816 ms 67228 KB Output is correct
23 Correct 826 ms 67192 KB Output is correct
24 Correct 812 ms 67320 KB Output is correct
25 Correct 818 ms 67088 KB Output is correct
26 Correct 846 ms 69688 KB Output is correct
27 Correct 866 ms 69620 KB Output is correct
28 Correct 817 ms 67064 KB Output is correct
29 Correct 807 ms 67320 KB Output is correct
30 Correct 808 ms 67192 KB Output is correct