답안 #52148

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
52148 2018-06-24T09:34:15 Z aquablitz11 벽 (IOI14_wall) C++14
100 / 100
942 ms 59580 KB
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

const int N = 1<<21;
const int INF = 1e9;

int n, lo[N<<1], hi[N<<1], *ans;

void addtag(int p, int c, int d)
{
    int a = lo[p], b = hi[p];
    lo[p] = min(d, max(a, c));
    hi[p] = max(c, min(b, d));
}

void push(int p, int b, int e)
{
    if (b == e) {
        ans[b] = min(max(ans[b], lo[p]), hi[p]);
    } else {
        int m = (b+e)/2;
        addtag(p<<1, lo[p], hi[p]);
        addtag(p<<1|1, lo[p], hi[p]);
    }
    lo[p] = 0;
    hi[p] = INF;
}

void build(int p=1, int b=0, int e=n-1)
{
    hi[p] = INF;
    if (b == e)
        return;
    int m = (b+e)/2;
    build(p<<1, b, m);
    build(p<<1|1, m+1, e);
}

void update(int l, int r, int x, int y, int p=1, int b=0, int e=n-1)
{
    if (e < l || b > r)
        return;
    if (b >= l && e <= r) {
        addtag(p, x, y);
    } else {
        push(p, b, e);
        int m = (b+e)/2;
        update(l, r, x, y, p<<1, b, m);
        update(l, r, x, y, p<<1|1, m+1, e);
    }
}

void finish(int p=1, int b=0, int e=n-1)
{
    push(p, b, e);
    if (b == e)
        return;
    int m = (b+e)/2;
    finish(p<<1, b, m);
    finish(p<<1|1, m+1, e);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    ::n = n;
    ans = finalHeight;
    build();
    for (int i = 0; i < k; ++i) {
        if (op[i] == 1)
            update(left[i], right[i], height[i], INF);
        else
            update(left[i], right[i], 0, height[i]);
    }
    finish();

    return;
}

Compilation message

wall.cpp: In function 'void push(int, int, int)':
wall.cpp:22:13: warning: unused variable 'm' [-Wunused-variable]
         int m = (b+e)/2;
             ^
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 4 ms 612 KB Output is correct
3 Correct 4 ms 612 KB Output is correct
4 Correct 9 ms 904 KB Output is correct
5 Correct 9 ms 1344 KB Output is correct
6 Correct 9 ms 1344 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1344 KB Output is correct
2 Correct 179 ms 8684 KB Output is correct
3 Correct 210 ms 8684 KB Output is correct
4 Correct 596 ms 11416 KB Output is correct
5 Correct 386 ms 11920 KB Output is correct
6 Correct 350 ms 11964 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 11964 KB Output is correct
2 Correct 6 ms 11964 KB Output is correct
3 Correct 5 ms 11964 KB Output is correct
4 Correct 8 ms 11964 KB Output is correct
5 Correct 7 ms 11964 KB Output is correct
6 Correct 7 ms 11964 KB Output is correct
7 Correct 2 ms 11964 KB Output is correct
8 Correct 175 ms 11964 KB Output is correct
9 Correct 199 ms 11964 KB Output is correct
10 Correct 593 ms 11964 KB Output is correct
11 Correct 459 ms 11964 KB Output is correct
12 Correct 371 ms 12084 KB Output is correct
13 Correct 2 ms 12084 KB Output is correct
14 Correct 217 ms 12084 KB Output is correct
15 Correct 38 ms 12084 KB Output is correct
16 Correct 655 ms 12084 KB Output is correct
17 Correct 360 ms 12084 KB Output is correct
18 Correct 343 ms 12084 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12084 KB Output is correct
2 Correct 4 ms 12084 KB Output is correct
3 Correct 3 ms 12084 KB Output is correct
4 Correct 8 ms 12084 KB Output is correct
5 Correct 7 ms 12084 KB Output is correct
6 Correct 8 ms 12084 KB Output is correct
7 Correct 2 ms 12084 KB Output is correct
8 Correct 184 ms 12084 KB Output is correct
9 Correct 211 ms 12084 KB Output is correct
10 Correct 590 ms 12084 KB Output is correct
11 Correct 412 ms 12084 KB Output is correct
12 Correct 341 ms 12084 KB Output is correct
13 Correct 2 ms 12084 KB Output is correct
14 Correct 182 ms 12084 KB Output is correct
15 Correct 35 ms 12084 KB Output is correct
16 Correct 590 ms 12084 KB Output is correct
17 Correct 357 ms 12084 KB Output is correct
18 Correct 413 ms 12084 KB Output is correct
19 Correct 905 ms 59576 KB Output is correct
20 Correct 942 ms 59576 KB Output is correct
21 Correct 919 ms 59580 KB Output is correct
22 Correct 796 ms 59580 KB Output is correct
23 Correct 811 ms 59580 KB Output is correct
24 Correct 824 ms 59580 KB Output is correct
25 Correct 775 ms 59580 KB Output is correct
26 Correct 895 ms 59580 KB Output is correct
27 Correct 806 ms 59580 KB Output is correct
28 Correct 771 ms 59580 KB Output is correct
29 Correct 787 ms 59580 KB Output is correct
30 Correct 807 ms 59580 KB Output is correct