oj.uz

답안 #1112540

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1112540 2024-11-14T09:42:55 Z farica 벽 (IOI14_wall) C++14
8 / 100
 3000 ms 8264 KB 
#include <bits/stdc++.h>
#include <wall.h>

using namespace std;

const int MAX_N = 1e5;

struct Segm {
    int x, L, R;
};

vector<Segm>segm;

void push(int pos, int l, int r) {
    if(l==r) {
        if(segm[pos].L > segm[pos].x) segm[pos].x = segm[pos].L;
        if(segm[pos].R < segm[pos].x) segm[pos].x = segm[pos].R;
        segm[pos].L = 0, segm[pos].R = MAX_N;
        return;
    }
    int m = (l+r)/2;
    if(segm[pos].L) {
        if(segm[2*pos+1].L or segm[2*pos+1].R != MAX_N) push(2*pos+1, l, m);
        if(segm[2*pos+2].L or segm[2*pos+2].R != MAX_N) push(2*pos+2, m+1, r);
        segm[2*pos+1].L = max(segm[2*pos+1].L, segm[pos].L);
        segm[2*pos+2].L = max(segm[2*pos+2].L, segm[pos].L);
        segm[pos].L = 0;
    }
    if(segm[pos].R != MAX_N) {
        if(segm[2*pos+1].L or segm[2*pos+1].R != MAX_N) push(2*pos+1, l, m);
        if(segm[2*pos+2].L or segm[2*pos+2].R != MAX_N) push(2*pos+2, m+1, r);
        segm[2*pos+1].R = min(segm[2*pos+1].R, segm[pos].R);
        segm[2*pos+2].R = min(segm[2*pos+2].R, segm[pos].R);
        segm[pos].R = MAX_N;
    }
}

void update(int pos, int l, int r, int L, int R, int val, int type) {
    if(r < L or l > R) return;
    push(pos, l, r);
    if(l >= L && r <= R) {
        if(type == 1) segm[pos].L = max(segm[pos].L, val);
        else segm[pos].R = min(segm[pos].R, val);
        return;
    }
    int mid = (l+r)/2;
    update(2*pos+1, l, mid, L, R, val, type);
    update(2*pos+2, mid+1, r, L, R, val, type);
}

int query(int pos, int l, int r, int x) {
    push(pos, l, r);
    if(l == r) return segm[pos].x;
    int mid = (l+r)/2;
    if(mid >= x) return query(2*pos+1, l, mid, x);
    else return query(2*pos+2, mid+1, r, x);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    Segm tmp;
    tmp.x = 0;
    tmp.L = 0;
    tmp.R = MAX_N;
    segm.assign(8*n, tmp);
    for(int i=0; i<k; ++i) {
        update(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);
    }
}

/*signed main() {
    int op[4] = {1, 2, 1, 2}, left[4] = {1, 1, 0, 0}, right[4] = {2, 1, 9, 1}, height[4] = {4, 1, 2, 1};
    int finalHeight[10];
    buildWall(10, 4, op, left, right, height, finalHeight);
}*/

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 3 ms 336 KB Output is correct
4 Correct 163 ms 1484 KB Output is correct
5 Correct 146 ms 1528 KB Output is correct
6 Correct 149 ms 1360 KB Output is correct

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 85 ms 8264 KB Output is correct
3 Execution timed out 3061 ms 5456 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 4 ms 336 KB Output is correct
4 Correct 162 ms 1360 KB Output is correct
5 Correct 144 ms 1360 KB Output is correct
6 Correct 162 ms 1480 KB Output is correct
7 Correct 1 ms 504 KB Output is correct
8 Correct 84 ms 8264 KB Output is correct
9 Execution timed out 3068 ms 5448 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 3 ms 496 KB Output is correct
4 Correct 157 ms 1480 KB Output is correct
5 Correct 147 ms 1360 KB Output is correct
6 Correct 145 ms 1360 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 84 ms 8132 KB Output is correct
9 Execution timed out 3054 ms 5192 KB Time limit exceeded
10 Halted 0 ms 0 KB -