Submission #626106

#	Time	Username	Problem	Language	Result	Execution time	Memory
626106		Duy_e	Wall (IOI14_wall)	C++14	100 / 100	1061 ms	69536 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
#define ll long long
#define pii pair<ll, ll>
#define st first
#define nd second
#define file "test"
using namespace std;
const long long INF = 1e18;
const long long N = 2e6 + 5;

struct node {
    int ma, mi;

    void init(int x, int y) {
        ma = x;
        mi = y;
    }

} st[4 * N];

void down(int id) {
    int u = id << 1, v = id << 1 | 1;

    int t = st[id].mi;
    if (t != -1) {
        st[u].mi = max(t, st[u].mi);
        st[u].ma = max(t, st[u].ma);
        st[v].mi = max(t, st[v].mi);
        st[v].ma = max(t, st[v].ma);
    }

    st[id].mi = 0;

    t = st[id].ma;
    if (t != -1) {
        // cout << id << ": " << t << '\n';
        st[u].ma = min(t, st[u].ma);
        st[u].mi = min(t, st[u].mi);
        st[v].ma = min(t, st[v].ma);
        st[v].mi = min(t, st[v].mi);
    }

    st[id].ma = 1e9;
}

ll get(int id, int l, int r, int i) {
    if (l == r) return id;

    down(id);

    int mid = l + r >> 1;
    if (mid >= i) return get(id << 1, l, mid, i);
    return get(id << 1 | 1, mid + 1, r, i);
}

void upd(int id, int l, int r, int lef, int rig, int t, int v) {
    if (l > rig || r < lef) return;
    if (lef <= l && r <= rig) {
        if (t == 1) { // adding phase
            st[id].mi = max(st[id].mi, v);
            st[id].ma = max(st[id].ma, v);
        } 

        if (t == 2) { // removing phase
            // cout << "v: " << st[id].ma << ' ' << v << '\n';
            st[id].ma = min(st[id].ma, v);
            st[id].mi = min(st[id].mi, v);
        }

        return;
    }

    if (r != l)
        down(id);
    int mid = l + r >> 1;
    upd(id << 1, l, mid, lef, rig, t, v);
    upd(id << 1 | 1, mid + 1, r, lef, rig, t, v);
}

void build(int id, int l, int r) {
    st[id].init(1e9, 0);
    if (l == r) return;

    int mid = l + r >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
}

ll ans(int id) {
    if (st[id].mi == -1) return st[id].ma;
    return st[id].mi;    
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalheight[]) {

    build(1, 0, n - 1);

    for (int i = 0; i < k; i ++)
        upd(1, 0, n - 1, left[i], right[i], op[i], height[i]);

    for (int i = 0; i < n; i ++)
        finalheight[i] = ans(get(1, 0, n - 1, i));

}

// ll n, k;
// int l[N], r[N], h[N], fh[N], op[N];

// int main()
// {
//     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//     #ifndef ONLINE_JUDGE
//         freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
//     #endif
    
//     cin >> n >> k;
//     for (int i = 0; i < k; i ++)
//         cin >> op[i] >> l[i] >> r[i] >> h[i];

//     buildWall(n, k, op, l, r, h, fh);

//     for (int i = 0; i < n; i ++)   
//         cout << fh[i] << '\n';

//     return 0;
// }    

Compilation message (stderr)

wall.cpp: In function 'long long int get(int, int, int, int)':
wall.cpp:52:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |     int mid = l + r >> 1;
      |               ~~^~~
wall.cpp: In function 'void upd(int, int, int, int, int, int, int)':
wall.cpp:76:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |     int mid = l + r >> 1;
      |               ~~^~~
wall.cpp: In function 'void build(int, int, int)':
wall.cpp:85:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |     int mid = l + r >> 1;
      |               ~~^~~

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