Submission #516539

#	Time	Username	Problem	Language	Result	Execution time	Memory
516539		blue	Regions (IOI09_regions)	C++17	100 / 100	2736 ms	65848 KiB

regions

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using pii = pair<int, int>;
using vpii = vector<pii>;
#define sz(x) int(x.size())

const int maxN = 200'000;
const int maxR = 25'000;
// const int maxR = 500;

const int mns = 500;

const int maxL = 10 + (maxR/mns);

int N, R, Q;
vi H(1+maxN);
vi S(1+maxN);
vi children[1+maxN];

vi region_list[1+maxR];
vi norm(1+maxR, 0);
int large_ct = 0;

vvl large_bottom(1+maxL, vl(1 + maxR));

vvl large_top(1+maxL, vl(1 + maxR));

vi inc(1+maxL, 0);

vi dfs_order(1, 0);
vi order_index(1+maxN);
int dfs_ct = 0;

vi subtree(1+maxN, 1);

void dfs(int u)
{
    dfs_order.push_back(u);
    order_index[u] = ++dfs_ct;

    for(int l = 1; l <= large_ct; l++)
        large_top[l][H[u]] += inc[l];

    if(norm[H[u]])
        inc[norm[H[u]]]++;

    for(int v: children[u])
    {
        dfs(v);
        subtree[u] += subtree[v];
    }

    if(norm[H[u]])
        inc[norm[H[u]]]--;
}







int main()
{
    // cout << "done\n";
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> R >> Q;

    cin >> H[1];
    S[1] = 0;

    for(int i = 2; i <= N; i++)
    {
        cin >> S[i] >> H[i];
        children[S[i]].push_back(i);
    }


    for(int i = 1; i <= N; i++)
    {
        region_list[ H[i] ].push_back(i);
    }

    for(int r = 1; r <= R; r++)
    {
        if(sz(region_list[r]) >= mns)
        {
            norm[r] = ++large_ct;
        }
    }


    dfs(1);

    vi pos_list[1+N], neg_list[1+N];
    for(int u = 1; u <= N; u++)
    {
        neg_list[order_index[u] - 1].push_back(H[u]);
        pos_list[order_index[u] + subtree[u] - 1].push_back(H[u]);
    }

    // for(int u: dfs_order) cerr << u << ' ';
    // cerr << '\n';

    // for(int r = 1; r <= R; r++)
    // {
    //     cerr << "r = " << r << " : ";
    //     for(int i = 1; i <= N)
    // }

    inc = vi(1+large_ct, 0);
    for(int i = 0; i <= N; i++)
    {
        if(norm[H[dfs_order[i]]])
            inc[ norm[H[dfs_order[i]]] ]++;

        for(int j: neg_list[i])
            for(int l = 1; l <= large_ct; l++)
                large_bottom[l][j] -= inc[l];

        for(int j: pos_list[i])
            for(int l = 1; l <= large_ct; l++)
                large_bottom[l][j] += inc[l];

        // cerr << "i = " << i << ": " << dfs_order[i] << " \n";
        // for(int r = 1; r <= R; r++) cerr << inc[r] << ' ';
        // cerr << '\n';
    }

    vi point_list[1+R+1];
    vpii inc_list[1+R+1];

    for(int i = 1; i <= N; i++)
    {
        point_list[H[i]].push_back(order_index[i]);
        inc_list[H[i]].push_back({order_index[i] + 1, +1});
        inc_list[H[i]].push_back({order_index[i] + subtree[i], -1});
    }

    for(int r = 1; r <= R; r++)
    {
        sort(point_list[r].begin(), point_list[r].end());
        sort(inc_list[r].begin(), inc_list[r].end());
    }


    for(int q = 1; q <= Q; q++)
    {
        int r1, r2;
        cin >> r1 >> r2;

        if(norm[r1])
        {
            // cerr << "case 1\n";
            cout << large_top[norm[r1]][r2] << '\n';
        }
        else if(norm[r2])
        {
            // cerr << "case 2\n";
            cout << large_bottom[norm[r2]][r1] << '\n';
    }
        else
        {
            ll res = 0;
            ll curr = 0;

            int ii = -1;

            for(int p: point_list[r2])
            {
                while(ii+1 < sz(inc_list[r1]) && inc_list[r1][ii+1].first <= p)
                {
                    ii++;
                    curr += inc_list[r1][ii].second;
                }
                res += curr;
            }

            cout << res << '\n';
        }

        cout.flush();
    }

    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85