제출 #931203

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
931203		VMaksimoski008	Wall (IOI14_wall)	C++14	100 / 100	801 ms	120656 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
 
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long
 
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
 
const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;
const double eps = 1e-9;

struct SegTree {
    int n;
    vector<int> tree;
    vector<pii> lazy;

    SegTree(int _n) {
        n = _n;
        tree.resize(4*n+5, 0);
        lazy.resize(4*n+5, {1e9, -1});
    }

    void push(int u, int tl, int tr) {
        if(tl == tr) return ;

        if(lazy[u].first != 1e9) {
            tree[2*u] = min(tree[2*u], lazy[u].first);
            lazy[2*u].first = min(lazy[2*u].first, lazy[u].first);
            lazy[2*u].second = min(lazy[2*u].second, lazy[u].first);

            tree[2*u+1] = min(tree[2*u+1], lazy[u].first);
            lazy[2*u+1].first = min(lazy[2*u+1].first, lazy[u].first);
            lazy[2*u+1].second = min(lazy[2*u+1].second, lazy[u].first);
        }

        if(lazy[u].second != -1) {
            tree[2*u] = max(tree[2*u], lazy[u].second);
            lazy[2*u].first = max(lazy[2*u].first, lazy[u].second);
            lazy[2*u].second = max(lazy[2*u].second, lazy[u].second);

            tree[2*u+1] = max(tree[2*u+1], lazy[u].second);
            lazy[2*u+1].first = max(lazy[2*u+1].first, lazy[u].second);
            lazy[2*u+1].second = max(lazy[2*u+1].second, lazy[u].second);
        }

        lazy[u] = {1e9, -1};
    }

    void update(int u, int tl, int tr, int l, int r, int t, int v) {
        push(u, tl, tr);
        if(tl > tr || l > tr || tl > r) return ;

        if(l <= tl && tr <= r) {
            if(t == 1) {
                tree[u] = max(tree[u], v);
                lazy[u].first = max(lazy[u].first, v);
                lazy[u].second = max(lazy[u].second, v);
            } else {
                tree[u] = min(tree[u], v);
                lazy[u].first = min(lazy[u].first, v);
                lazy[u].second = min(lazy[u].second, v);
            }

            push(u, tl, tr);
            return ;
        }

        int tm = (tl + tr) / 2;
        update(2*u, tl, tm, l, r, t, v);
        update(2*u+1, tm+1, tr, l, r, t, v);
    }

    int query(int u, int tl, int tr, int p) {
        if(tl == tr) return tree[u];
        push(u, tl, tr);
        int tm = (tl + tr) / 2;
        if(p <= tm) return query(2*u, tl, tm, p);
        return query(2*u+1, tm+1, tr, p);
    }   

    void update(int l, int r, int t, int v) { update(1, 0, n-1, l, r, t, v); }
    int query(int p) { return query(1, 0, n-1, p); }
};
 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    for(int i=0; i<n; i++) finalHeight[i] = 0;

    SegTree tree(n);
 
    for(int i=0; i<k; i++)
        tree.update(left[i], right[i], op[i], height[i]);
    for(int i=0; i<n; i++)
        finalHeight[i] = tree.query(i);
}
 
// int32_t main() {
//     int n, k;
//     cin >> n >> k;
 
//     int op[n], left[n], right[n], height[n], finalHeight[n];
 
//     for(int i=0; i<k; i++)
//         cin >> op[i] >> left[i] >> right[i] >> height[i];
 
//     buildWall(n, k, op, left, right, height, finalHeight);
//     return 0;
// }

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39