Submission #578475

#	Time	Username	Problem	Language	Result	Execution time	Memory
578475		tranxuanbach	Wall (IOI14_wall)	C++17	100 / 100	1567 ms	159984 KiB

wall

#ifndef FEXT

#include "wall.h"

#endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = l; i < r; i++)
#define ForE(i, l, r) for (auto i = l; i <= r; i++)
#define FordE(i, l, r) for (auto i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pair <int, int>>;
using vvi = vector <vector <int>>;

struct toi_la_nguoi_trung_quoc{
    struct segnode_t{
        int mx, mx2, cntmx;
        int mn, mn2, cntmn;
        int lazymx, lazymn;

        segnode_t(int x = 0){
            mx = x; mx2 = INT_MIN; cntmx = 1;
            mn = x; mn2 = INT_MAX; cntmn = 1;
            lazymx = lazymn = -1;
        }

        friend segnode_t merge(const segnode_t &lhs, const segnode_t &rhs){
            segnode_t cac;
            cac.mx = max(lhs.mx, rhs.mx);
            cac.mx2 = max(lhs.mx == cac.mx ? lhs.mx2 : lhs.mx, rhs.mx == cac.mx ? rhs.mx2 : rhs.mx);
            cac.cntmx = (lhs.mx == cac.mx ? lhs.cntmx : 0) + (rhs.mx == cac.mx ? rhs.cntmx : 0);
            cac.mn = min(lhs.mn, rhs.mn);
            cac.mn2 = min(lhs.mn == cac.mn ? lhs.mn2 : lhs.mn, rhs.mn == cac.mn ? rhs.mn2 : rhs.mn);
            cac.cntmn = (lhs.mn == cac.mn ? lhs.cntmn : 0) + (rhs.mn == cac.mn ? rhs.cntmn : 0);
            cac.lazymx = cac.lazymn = -1;
            return cac;
        }

        friend ostream& operator<< (ostream& out, const segnode_t &rhs){
            out << '{';
            out << rhs.mx << ' ' << rhs.mx2 << ' '  << rhs.cntmx << ' ' << rhs.mn << ' ' << rhs.mn2 << ' ' << rhs.cntmn << ' ' << rhs.lazymx << ' ' << rhs.lazymn;
            out << '}';
            return out;
        }
    };

    segnode_t seg[1 << 22];

    void build(int id, int l, int r){
        if (l == r){
            seg[id] = segnode_t(0);
            return;
        }
        int mid = (l + r) >> 1;
        build(id * 2, l, mid);
        build(id * 2 + 1, mid + 1, r);
        seg[id] = merge(seg[id * 2], seg[id * 2 + 1]);
    }

    void down(int id, bool debug = 0){
        if (debug) cout << "down " << id << endl;
        if (debug) cout << seg[id] << endl << seg[id * 2] << endl << seg[id * 2 + 1] << endl;
        int mx = max(seg[id * 2].mx, seg[id * 2 + 1].mx);
        int mn = min(seg[id * 2].mn, seg[id * 2 + 1].mn);
        if (seg[id].lazymx != -1 and seg[id * 2].mx == mx){
            seg[id * 2].mx = seg[id].lazymx;
            seg[id * 2].lazymx = seg[id].lazymx;
            if (seg[id * 2].mx2 == INT_MIN or seg[id * 2].mn2 == INT_MAX){
                seg[id * 2].mn = seg[id].lazymx;
                seg[id * 2].lazymn = seg[id].lazymx;
            }
        }
        if (seg[id].lazymn != -1 and seg[id * 2].mn == mn){
            seg[id * 2].mn = seg[id].lazymn;
            seg[id * 2].lazymn = seg[id].lazymn;
            if (seg[id * 2].mx2 == INT_MIN or seg[id * 2].mn2 == INT_MAX){
                seg[id * 2].mx = seg[id].lazymn;
                seg[id * 2].lazymx = seg[id].lazymn;
            }
        }
        if (seg[id * 2].mn != seg[id * 2].mx){
            seg[id * 2].mn2 = min(seg[id * 2].mn2, seg[id * 2].mx);
            seg[id * 2].mx2 = max(seg[id * 2].mx2, seg[id * 2].mn);
        }
        if (seg[id].lazymx != -1 and seg[id * 2 + 1].mx == mx){
            seg[id * 2 + 1].mx = seg[id].lazymx;
            seg[id * 2 + 1].lazymx = seg[id].lazymx;
            if (seg[id * 2 + 1].mx2 == INT_MIN or seg[id * 2 + 1].mn2 == INT_MAX){
                seg[id * 2 + 1].mn = seg[id].lazymx;
                seg[id * 2 + 1].lazymn = seg[id].lazymx;
            }
        }
        if (seg[id].lazymn != -1 and seg[id * 2 + 1].mn == mn){
            seg[id * 2 + 1].mn = seg[id].lazymn;
            seg[id * 2 + 1].lazymn = seg[id].lazymn;
            if (seg[id * 2 + 1].mx2 == INT_MIN or seg[id * 2 + 1].mn2 == INT_MAX){
                seg[id * 2 + 1].mx = seg[id].lazymn;
                seg[id * 2 + 1].lazymx = seg[id].lazymn;
            }
        }
        if (seg[id * 2 + 1].mn != seg[id * 2 + 1].mx){
            seg[id * 2 + 1].mn2 = min(seg[id * 2 + 1].mn2, seg[id * 2 + 1].mx);
            seg[id * 2 + 1].mx2 = max(seg[id * 2 + 1].mx2, seg[id * 2 + 1].mn);
        }
        seg[id].lazymx = seg[id].lazymn = -1;
        if (debug) cout << seg[id] << endl << seg[id * 2] << endl << seg[id * 2 + 1] << endl;
    }

    void update_smax(int id, int l, int r, int u, int v, int x, bool debug = 0, bool debugdown = 0){
        if (v < l or r < u or seg[id].mn >= x){
            return;
        }
        if (debug) cout << "update_smax " << id << ' ' << l << ' ' << r << ' ' << u << ' ' << v << ' ' << x << endl;
        if (debug) cout << seg[id] << endl;
        if (u <= l and r <= v and seg[id].mn2 > x){
            seg[id].lazymn = x;
            seg[id].mn = x;
            if (seg[id].mn2 == INT_MAX){
                seg[id].lazymx = x;
                seg[id].mx = x;
            }
            if (seg[id].mn != seg[id].mx){
                seg[id].mn2 = min(seg[id].mn2, seg[id].mx);
                seg[id].mx2 = max(seg[id].mx2, seg[id].mn);
            }
            if (debug) cout << "update_smax assign " << id << ' ' << seg[id] << endl;
            return;
        }
        down(id, debugdown);
        int mid = (l + r) >> 1;
        update_smax(id * 2, l, mid, u, v, x, debug, debugdown);
        update_smax(id * 2 + 1, mid + 1, r, u, v, x, debug, debugdown);
        seg[id] = merge(seg[id * 2], seg[id * 2 + 1]);
        if (debug) cout << "update_smax merge " << id << ' ' << seg[id] << endl;
    }

    void update_smin(int id, int l, int r, int u, int v, int x, bool debug = 0, bool debugdown = 0){
        if (v < l or r < u or seg[id].mx <= x){
            return;
        }
        if (debug) cout << "update_smin " << id << ' ' << l << ' ' << r << ' ' << u << ' ' << v << ' ' << x << endl;
        if (debug) cout << seg[id] << endl;
        if (u <= l and r <= v and seg[id].mx2 < x){
            seg[id].lazymx = x;
            seg[id].mx = x;
            if (seg[id].mx2 == INT_MIN){
                seg[id].lazymn = x;
                seg[id].mn = x;
            }
            if (seg[id].mn != seg[id].mx){
                seg[id].mn2 = min(seg[id].mn2, seg[id].mx);
                seg[id].mx2 = max(seg[id].mx2, seg[id].mn);
            }
            if (debug) cout << "update_smin assign " << id << ' ' << seg[id] << endl;
            return;
        }
        down(id, debugdown);
        int mid = (l + r) >> 1;
        update_smin(id * 2, l, mid, u, v, x, debug, debugdown);
        update_smin(id * 2 + 1, mid + 1, r, u, v, x, debug, debugdown);
        seg[id] = merge(seg[id * 2], seg[id * 2 + 1]);
        if (debug) cout << "update_smin merge " << id << ' ' << seg[id] << endl;
    }

    int get(int id, int l, int r, int i, bool debug = 0, bool debugdown = 0){
        if (l == r){
            return seg[id].mx;
        }
        down(id, debugdown);
        int mid = (l + r) >> 1;
        if (i <= mid){
            return get(id * 2, l, mid, i, debug, debugdown);
        }
        else{
            return get(id * 2 + 1, mid + 1, r, i, debug, debugdown);
        }
    }
} seg;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    seg.build(1, 0, n - 1);
    For(i, 0, k){
        if (op[i] == 1){
            seg.update_smax(1, 0, n - 1, left[i], right[i], height[i]);
        }
        else if (op[i] == 2){
            seg.update_smin(1, 0, n - 1, left[i], right[i], height[i]);
        }
        // For(j, 0, n){
        //     cout << seg.get(1, 0, n - 1, j) << ' ';
        // } cout << endl;
    }
    For(i, 0, n){
        finalHeight[i] = seg.get(1, 0, n - 1, i);
    }
    return;
}

#ifdef FEXT

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    freopen("KEK.inp", "r", stdin);
    freopen("KEK.out", "w", stdout);
    int n, k; cin >> n >> k;
    int op[k], left[k], right[k], height[k];
    For(i, 0, k){
        cin >> op[i] >> left[i] >> right[i] >> height[i];
    }
    int finalHeight[n];
    buildWall(n, k, op, left, right, height, finalHeight);
    For(i, 0, n){
        cout << finalHeight[i] << ' ';
    } cout << endl;
}

#endif

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

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