Submission #1150062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150062		monkey133	Vinjete (COI22_vinjete)	C++20	100 / 100	212 ms	39056 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Node {
    ll mn, cnt, lazy;
};

vector<Node> seg;  // Array-based segment tree
vector<ll> comp;   // Compressed coordinates

// Build the segment tree over the range [l, r] in the compressed domain.
void build(int idx, int l, int r) {
    if(l == r) {
        seg[idx].mn = 0;
        // The segment [comp[l], comp[l+1]-1] has length = comp[l+1]-comp[l]
        seg[idx].cnt = comp[l+1] - comp[l];
        seg[idx].lazy = 0;
        return;
    }
    int mid = (l + r) / 2;
    build(idx * 2, l, mid);
    build(idx * 2 + 1, mid + 1, r);
    seg[idx].lazy = 0;
    // Merge children
    if(seg[idx * 2].mn == seg[idx * 2 + 1].mn) {
        seg[idx].mn = seg[idx * 2].mn;
        seg[idx].cnt = seg[idx * 2].cnt + seg[idx * 2 + 1].cnt;
    } else if(seg[idx * 2].mn < seg[idx * 2 + 1].mn) {
        seg[idx].mn = seg[idx * 2].mn;
        seg[idx].cnt = seg[idx * 2].cnt;
    } else {
        seg[idx].mn = seg[idx * 2 + 1].mn;
        seg[idx].cnt = seg[idx * 2 + 1].cnt;
    }
}

void push_down(int idx, int l, int r) {
    if(seg[idx].lazy != 0) {
        int mid = (l + r) / 2;
        seg[idx * 2].mn += seg[idx].lazy;
        seg[idx * 2].lazy += seg[idx].lazy;
        seg[idx * 2 + 1].mn += seg[idx].lazy;
        seg[idx * 2 + 1].lazy += seg[idx].lazy;
        seg[idx].lazy = 0;
    }
}

void update(int idx, int l, int r, int ql, int qr, ll val) {
    if(ql > r || qr < l)
        return;
    if(ql <= l && r <= qr) {
        seg[idx].mn += val;
        seg[idx].lazy += val;
        return;
    }
    push_down(idx, l, r);
    int mid = (l + r) / 2;
    update(idx * 2, l, mid, ql, qr, val);
    update(idx * 2 + 1, mid + 1, r, ql, qr, val);
    if(seg[idx * 2].mn == seg[idx * 2 + 1].mn) {
        seg[idx].mn = seg[idx * 2].mn;
        seg[idx].cnt = seg[idx * 2].cnt + seg[idx * 2 + 1].cnt;
    } else if(seg[idx * 2].mn < seg[idx * 2 + 1].mn) {
        seg[idx].mn = seg[idx * 2].mn;
        seg[idx].cnt = seg[idx * 2].cnt;
    } else {
        seg[idx].mn = seg[idx * 2 + 1].mn;
        seg[idx].cnt = seg[idx * 2 + 1].cnt;
    }
}
 
// For the tree we use an undirected adjacency list.
struct Edge {
    int to;
    ll l, r;
};

int n;
ll M;
vector<vector<Edge>> adj;
vector<ll> ans;
int segSize; // number of segments = comp.size()-1

// DFS on the tree. For each edge, we update the segment tree for the interval [l, r].
// At each node, the answer is M minus the total length of indices that are still 0.
void dfs(int v, int p) {
    // The root of our segment tree covers the entire compressed domain.
    // If the minimum value is <= 0, then seg[1].cnt is the total uncovered length.
    ll uncovered = (seg[1].mn <= 0 ? seg[1].cnt : 0);
    ans[v] = M - uncovered;
    for(auto &edge : adj[v]) {
        if(edge.to == p)
            continue;
        // Find the compressed indices for the interval [edge.l, edge.r]
        int L = int(lower_bound(comp.begin(), comp.end(), edge.l) - comp.begin());
        int R = int(lower_bound(comp.begin(), comp.end(), edge.r + 1) - comp.begin()) - 1;
        update(1, 0, segSize - 1, L, R, 1);
        dfs(edge.to, v);
        update(1, 0, segSize - 1, L, R, -1);
    }
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> M;
    adj.resize(n + 1);
    ans.resize(n + 1, 0);
    
    // Read edges and also gather all endpoints for compression.
    for(int i = 1; i < n; i++){
        int u, v;
        ll l, r;
        cin >> u >> v >> l >> r;
        // Since the tree is undirected, add both directions.
        adj[u].push_back({v, l, r});
        adj[v].push_back({u, l, r});
        comp.push_back(l);
        comp.push_back(r + 1); // we use half-open intervals [l, r+1)
    }
    // Also include the boundaries of the whole range.
    comp.push_back(1);
    comp.push_back(M + 1);
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    
    // The leaves of our segment tree correspond to intervals [comp[i], comp[i+1]-1]
    segSize = comp.size() - 1;
    seg.resize(segSize * 4);
    build(1, 0, segSize - 1);
    
    dfs(1, -1);
    for(int i = 2; i <= n; i++)
        cout << ans[i] << "\n";
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 29 / 29
• Subtask 5: 31 / 31