Submission #1091017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091017		VMaksimoski008	Min-max tree (BOI18_minmaxtree)	C++17	22 / 100	126 ms	18888 KiB

minmaxtree

#include <bits/stdc++.h>

#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 pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 7e4 + 5;

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

    SegTree(int _n) : n(_n), tree(4*_n, { 0, 1e9 }), lazy(4*_n, { 0, 1e9 }) {}

    pii merge(pii a, pii b) {
        return { max(a.first, b.first), min(a.second, b.second) };
    }

    void push(int u, int tl, int tr) {
        if(lazy[u] == pii{ 0, 1e9 }) return ;
        tree[u] = merge(tree[u], lazy[u]);

        if(tl != tr) {
            lazy[2*u] = merge(lazy[2*u], lazy[u]);
            lazy[2*u+1] = merge(lazy[2*u+1], lazy[u]);
        }

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

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

        if(l <= tl && tr <= r) {
            lazy[u] = merge(lazy[u], v);
            push(u, tl, tr);
            return ;
        }

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

    pii query(int u, int tl, int tr, int l, int r) {
        if(l > tr || tl > r) return { 0, 1e9 };
        push(u, tl, tr);
        if(l <= tl && tr <= r) return tree[u];
        int tm = (tl + tr) / 2;
        return merge(query(2*u, tl, tm, l, r), query(2*u+1, tm+1, tr, l, r));
    }

    void update(int l, int r, pii v) { update(1, 0, n-1, l, r, v); }
    pii query(int l, int r) { return query(1, 0, n-1, l, r); }
};

int n, d[maxn], t[maxn], par[maxn], sub[maxn], in[maxn], timer=0, MN[maxn], MX[maxn];
vector<int> graph[maxn];
vector<pii> edges;

int dfs(int u, int p) {
    sub[u] = 1;
    for(int &v : graph[u]) {
        if(v == p) continue;
        d[v] = d[u] + 1;
        par[v] = u;
        sub[u] += dfs(v, u);
    }
    return sub[u];
}

void hld(int u, int p, int h) {
    in[u] = timer++;
    t[u] = h;

    int ch = 0;
    for(int &v : graph[u]) {
        if(v == p) continue;
        if(sub[v] > sub[ch]) ch = v;
    }

    if(ch) hld(ch, u, h);
    for(int &v : graph[u]) {
        if(v == p || v == ch) continue;
        hld(v, u, v);
    }
}

signed main() { 
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int n; cin >> n;
    for(int i=0; i<n-1; i++) {
        int a, b; cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
        edges.push_back({ a, b });
    }

    dfs(1, 1);
    hld(1, 1, 1);

    SegTree tree(n);
    int q; cin >> q;
    while(q--) {
        char ch;
        int u, v, x;
        cin >> ch >> u >> v >> x;

        while(t[u] != t[v]) {
            if(d[t[u]] < d[t[v]]) swap(u, v);
            tree.update(in[t[u]], in[u], (ch == 'M' ? pii{ 0, x } : pii{ x, 1e9 }));
            u = par[t[u]];
        }

        if(d[u] > d[v]) swap(u, v);
        tree.update(in[u]+1, in[v], (ch == 'M' ? pii{ 0, x } : pii{ x, 1e9 }));
    }

    for(int i=1; i<=n; i++) {
        auto res = tree.query(in[i], in[i]);
        MN[i] = res.first; MX[i] = res.second;
    }
    for(auto &x : edges) {
        if(d[x.first] > d[x.second]) swap(x.first, x.second);
        cout << x.first << " " << x.second << " " << MX[x.second] << '\n';
    }
    return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 22 / 22
• Subtask 3: 0 / 29
• Subtask 4: 0 / 42