Submission #1195533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195533		raphaelp	Vinjete (COI22_vinjete)	C++20	100 / 100	291 ms	34596 KiB

Main

#include <bits/stdc++.h>
using namespace std;
class SegTree
{
private:
    int N, cur = 2;
    vector<int> st, minn, lazy;
    int l(int x) { return (x << 1); }
    int r(int x) { return (x << 1) + 1; }
    void propagate(int L, int R, int x)
    {
        minn[x] += lazy[x];
        if (L != R)
        {
            lazy[l(x)] += lazy[x];
            lazy[r(x)] += lazy[x];
        }
        lazy[x] = 0;
    }
    void update(int L, int R, int a, int b, int val, int x)
    {
        propagate(L, R, x);
        if (L > b || R < a)
            return;
        if (L >= a && R <= b)
        {
            lazy[x] += val;
            propagate(L, R, x);
        }
        else
        {
            int m = (L + R) / 2;
            update(L, m, a, b, val, l(x));
            update(m + 1, R, a, b, val, r(x));
            minn[x] = min(minn[l(x)], minn[r(x)]);
            st[x] = 0;
            if (minn[l(x)] == minn[x])
                st[x] += st[l(x)];
            if (minn[r(x)] == minn[x])
                st[x] += st[r(x)];
        }
    }

public:
    SegTree(vector<int> &A)
    {
        N = pow(2, ceil(log2(A.size())));
        st.assign(2 * N, 0);
        minn.assign(2 * N, 0);
        lazy.assign(2 * N, 0);
        for (int i = N; i < N + A.size(); i++)
            st[i] = A[i - N];
        for (int i = N - 1; i > 0; i--)
            st[i] = st[l(i)] + st[r(i)];
    }
    void update(int a, int b, int val) { update(0, N - 1, a, b, val, 1); }
    int Q() { return ((minn[1] == 0) ? st[1] : 0); }
};
void dfs(int x, int p, vector<vector<vector<int>>> &AR, SegTree &ST, vector<int> &ans)
{
    ans[x] = ST.Q();
    for (int i = 0; i < AR[x].size(); i++)
    {
        if (AR[x][i][0] == p)
            continue;
        ST.update(AR[x][i][1], AR[x][i][2] - 1, 1);
        dfs(AR[x][i][0], x, AR, ST, ans);
        ST.update(AR[x][i][1], AR[x][i][2] - 1, -1);
    }
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int N, M;
    cin >> N >> M;
    vector<vector<vector<int>>> AR(N);
    vector<int> imp;
    for (int i = 0; i < N - 1; i++)
    {
        int a, b, l, r;
        cin >> a >> b >> l >> r;
        a--, b--;
        imp.push_back(l - 1);
        imp.push_back(r);
        AR[a].push_back({b, l - 1, r});
        AR[b].push_back({a, l - 1, r});
    }
    sort(imp.begin(), imp.end());
    vector<int> pond, imp2(1, -1);
    int last = 0;
    for (int i = 0; i < imp.size(); i++)
    {
        if (i == 0 || imp[i] != imp[i - 1])
        {
            imp2.push_back(imp[i]);
            pond.push_back(imp[i] - last);
            last = imp[i];
        }
    }
    pond.push_back(M - last);
    swap(imp, imp2);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < AR[i].size(); j++)
        {
            AR[i][j][1] = lower_bound(imp.begin(), imp.end(), AR[i][j][1]) - imp.begin();
            AR[i][j][2] = lower_bound(imp.begin(), imp.end(), AR[i][j][2]) - imp.begin();
        }
    }
    SegTree ST(pond);
    vector<int> ans(N);
    dfs(0, 0, AR, ST, ans);
    for (int i = 1; i < N; i++)
        cout << M - ans[i] << '\n';
}

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