oj.uz

Submission #578475

# Submission time Handle Problem Language Result Execution time Memory
578475 2022-06-17T04:02:44 Z tranxuanbach Wall (IOI14_wall) C++17
100 / 100
 1567 ms 159984 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 131596 KB Output is correct
2 Correct 59 ms 131644 KB Output is correct
3 Correct 63 ms 131536 KB Output is correct
4 Correct 68 ms 131788 KB Output is correct
5 Correct 72 ms 131728 KB Output is correct
6 Correct 66 ms 131868 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 131532 KB Output is correct
2 Correct 216 ms 139388 KB Output is correct
3 Correct 150 ms 134908 KB Output is correct
4 Correct 243 ms 139968 KB Output is correct
5 Correct 295 ms 140508 KB Output is correct
6 Correct 341 ms 140552 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 131556 KB Output is correct
2 Correct 68 ms 131600 KB Output is correct
3 Correct 66 ms 131528 KB Output is correct
4 Correct 66 ms 131720 KB Output is correct
5 Correct 67 ms 131748 KB Output is correct
6 Correct 72 ms 131780 KB Output is correct
7 Correct 65 ms 131528 KB Output is correct
8 Correct 188 ms 141740 KB Output is correct
9 Correct 136 ms 137208 KB Output is correct
10 Correct 267 ms 142284 KB Output is correct
11 Correct 262 ms 142820 KB Output is correct
12 Correct 341 ms 142756 KB Output is correct
13 Correct 63 ms 131496 KB Output is correct
14 Correct 207 ms 141644 KB Output is correct
15 Correct 102 ms 132748 KB Output is correct
16 Correct 835 ms 142528 KB Output is correct
17 Correct 485 ms 142532 KB Output is correct
18 Correct 615 ms 142564 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 131484 KB Output is correct
2 Correct 65 ms 131660 KB Output is correct
3 Correct 57 ms 131620 KB Output is correct
4 Correct 91 ms 131664 KB Output is correct
5 Correct 87 ms 131652 KB Output is correct
6 Correct 66 ms 131792 KB Output is correct
7 Correct 66 ms 131528 KB Output is correct
8 Correct 197 ms 141676 KB Output is correct
9 Correct 148 ms 137240 KB Output is correct
10 Correct 286 ms 142408 KB Output is correct
11 Correct 269 ms 142784 KB Output is correct
12 Correct 355 ms 142880 KB Output is correct
13 Correct 58 ms 131604 KB Output is correct
14 Correct 211 ms 141696 KB Output is correct
15 Correct 101 ms 132696 KB Output is correct
16 Correct 836 ms 142580 KB Output is correct
17 Correct 533 ms 142572 KB Output is correct
18 Correct 506 ms 142536 KB Output is correct
19 Correct 1517 ms 159916 KB Output is correct
20 Correct 1539 ms 157488 KB Output is correct
21 Correct 1491 ms 159952 KB Output is correct
22 Correct 1475 ms 157480 KB Output is correct
23 Correct 1531 ms 157424 KB Output is correct
24 Correct 1567 ms 157364 KB Output is correct
25 Correct 1522 ms 157380 KB Output is correct
26 Correct 1543 ms 159984 KB Output is correct
27 Correct 1491 ms 159920 KB Output is correct
28 Correct 1534 ms 157444 KB Output is correct
29 Correct 1475 ms 157424 KB Output is correct
30 Correct 1477 ms 157368 KB Output is correct