oj.uz

답안 #731431

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
731431 2023-04-27T12:27:54 Z Desh03 벽 (IOI14_wall) C++17
100 / 100
 602 ms 75744 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

struct segtree {
    vector<int> st, t, o;
    int sz;
    segtree(int n) {
        sz = n;
        while (__builtin_popcount(sz) ^ 1) sz++;
        st.resize(sz << 1), o.resize(sz << 1, -1), t.resize(sz << 1);
    }
    void change(int v, int h, int op) {
        if (op == 4) {
            st[v] = h, o[v] = 4;
        } else if (o[v] == -1) {
            if (op == 2) {
                st[v] = 1e9, t[v] = h, o[v] = 1;
            } else {
                st[v] = h, t[v] = -1e9, o[v] = 0;
            }
        } else if (o[v] == 4) {
            if (op == 2) {
                st[v] = max(st[v], h);
            } else {
                st[v] = min(st[v], h);
            }
            t[v] = st[v];
        } else {
            if (op == 2) {
                t[v] = max(t[v], h);
                if (t[v] >= st[v]) {
                    st[v] = t[v];
                    o[v] = 4;
                }
            } else {
                st[v] = min(st[v], h);
                if (t[v] >= st[v]) {
                    t[v] = st[v];
                    o[v] = 4;
                }
            }
        }
    }
    void push(int v) {
        if ((v << 1) >= sz) {
            if (o[v] == 1) {
                st[v << 1] = min(st[v << 1], st[v]);
                st[v << 1] = max(st[v << 1], t[v]);
                st[v << 1 | 1] = min(st[v << 1 | 1], st[v]);
                st[v << 1 | 1] = max(st[v << 1 | 1], t[v]);
            } else if (o[v] == 0) {
                st[v << 1] = max(st[v << 1], t[v]);
                st[v << 1] = min(st[v << 1], st[v]);
                st[v << 1 | 1] = max(st[v << 1 | 1], t[v]);
                st[v << 1 | 1] = min(st[v << 1 | 1], st[v]);
            } else {
                st[v << 1] = st[v];
                st[v << 1 | 1] = st[v];
            }
        } else {
            if (o[v] == 1) {
                change(v << 1, st[v], 3);
                change(v << 1, t[v], 2);
                change(v << 1 | 1, st[v], 3);
                change(v << 1 | 1, t[v], 2);
            } else if (o[v] == 0) {
                change(v << 1, t[v], 2);
                change(v << 1, st[v], 3);
                change(v << 1 | 1, t[v], 2);
                change(v << 1 | 1, st[v], 3);
            } else {
                change(v << 1, st[v], 4);
                change(v << 1 | 1, st[v], 4);
            }
        }
        o[v] = -1;
    }
    void upd(int v, int l, int r, int ql, int qr, int op, int h) {
        if (l > qr || r < ql) return;
        if (l >= ql && r <= qr) {
            if (v < sz) change(v, h, op + 1);
            else {
                if (op == 2) st[v] = min(st[v], h);
                else st[v] = max(st[v], h);
            }
            return;
        }
        if (o[v] != -1) push(v);
        int m = l + r >> 1;
        upd(v << 1, l, m, ql, qr, op, h);
        upd(v << 1 | 1, m + 1, r, ql, qr, op, h);
    }
    void pushdown(int v) {
        if (v >= sz) return;
        if (o[v] != -1) push(v);
        pushdown(v << 1);
        pushdown(v << 1 | 1);
    }
    void upd(int l, int r, int op, int h) {
        upd(1, 0, sz - 1, l, r, op, h);
    }
    int get(int i) {
        return st[i + sz];
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int hieght[], int finalhieght[]) {
    segtree st(n);
    for (int i = 0; i < k; i++)
        st.upd(left[i], right[i], op[i], hieght[i]);
    st.pushdown(1);
    for (int i = 0; i < n; i++) finalhieght[i] = st.get(i);
}

Compilation message

wall.cpp: In member function 'void segtree::upd(int, int, int, int, int, int, int)':
wall.cpp:90:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |         int m = l + r >> 1;
      |                 ~~^~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 2 ms 312 KB Output is correct
4 Correct 6 ms 824 KB Output is correct
5 Correct 4 ms 828 KB Output is correct
6 Correct 4 ms 852 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 138 ms 13840 KB Output is correct
3 Correct 199 ms 8100 KB Output is correct
4 Correct 602 ms 21216 KB Output is correct
5 Correct 213 ms 21724 KB Output is correct
6 Correct 209 ms 20176 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 432 KB Output is correct
3 Correct 2 ms 312 KB Output is correct
4 Correct 9 ms 852 KB Output is correct
5 Correct 5 ms 828 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 137 ms 13916 KB Output is correct
9 Correct 198 ms 8288 KB Output is correct
10 Correct 596 ms 21264 KB Output is correct
11 Correct 208 ms 21708 KB Output is correct
12 Correct 203 ms 20188 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 141 ms 13912 KB Output is correct
15 Correct 30 ms 2148 KB Output is correct
16 Correct 485 ms 21224 KB Output is correct
17 Correct 208 ms 20632 KB Output is correct
18 Correct 211 ms 20576 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 5 ms 884 KB Output is correct
5 Correct 5 ms 824 KB Output is correct
6 Correct 5 ms 980 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 140 ms 13884 KB Output is correct
9 Correct 201 ms 8116 KB Output is correct
10 Correct 581 ms 21332 KB Output is correct
11 Correct 222 ms 21708 KB Output is correct
12 Correct 206 ms 20172 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 140 ms 13836 KB Output is correct
15 Correct 36 ms 2136 KB Output is correct
16 Correct 483 ms 21088 KB Output is correct
17 Correct 222 ms 20552 KB Output is correct
18 Correct 206 ms 20600 KB Output is correct
19 Correct 497 ms 75588 KB Output is correct
20 Correct 491 ms 75632 KB Output is correct
21 Correct 516 ms 75632 KB Output is correct
22 Correct 500 ms 75564 KB Output is correct
23 Correct 493 ms 75632 KB Output is correct
24 Correct 495 ms 75632 KB Output is correct
25 Correct 492 ms 75660 KB Output is correct
26 Correct 513 ms 75724 KB Output is correct
27 Correct 528 ms 75596 KB Output is correct
28 Correct 499 ms 75616 KB Output is correct
29 Correct 493 ms 75744 KB Output is correct
30 Correct 516 ms 75540 KB Output is correct