oj.uz

Submission #516501

# Submission time Handle Problem Language Result Execution time Memory
516501 2022-01-21T12:27:56 Z blue Regions (IOI09_regions) C++17
90 / 100
 2737 ms 82680 KB 
#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 = 400;

const int maxL = 1 + 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];
    vpii inc_list[1+R];

    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});
        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]) cout << large_top[norm[r1]][r2] << '\n';
        else if(norm[r2]) 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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 34068 KB Output is correct
2 Correct 19 ms 34024 KB Output is correct
3 Correct 21 ms 34024 KB Output is correct
4 Correct 20 ms 34120 KB Output is correct
5 Correct 27 ms 34168 KB Output is correct
6 Correct 35 ms 34236 KB Output is correct
7 Correct 59 ms 34308 KB Output is correct
8 Correct 47 ms 34436 KB Output is correct
9 Correct 46 ms 34988 KB Output is correct
10 Correct 101 ms 35672 KB Output is correct
11 Correct 83 ms 36440 KB Output is correct
12 Correct 117 ms 37328 KB Output is correct
13 Correct 189 ms 37944 KB Output is correct
14 Correct 195 ms 38992 KB Output is correct
15 Correct 223 ms 41124 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 860 ms 45492 KB Output is correct
2 Correct 1006 ms 46072 KB Output is correct
3 Correct 1678 ms 47720 KB Output is correct
4 Correct 268 ms 39108 KB Output is correct
5 Correct 447 ms 40032 KB Output is correct
6 Correct 671 ms 42296 KB Output is correct
7 Correct 1103 ms 45580 KB Output is correct
8 Runtime error 75 ms 76720 KB Execution killed with signal 11
9 Correct 1364 ms 59208 KB Output is correct
10 Runtime error 91 ms 82680 KB Execution killed with signal 11
11 Correct 2737 ms 66608 KB Output is correct
12 Correct 1116 ms 63912 KB Output is correct
13 Correct 1402 ms 63724 KB Output is correct
14 Correct 1689 ms 65864 KB Output is correct
15 Correct 2181 ms 67024 KB Output is correct
16 Correct 1955 ms 66804 KB Output is correct
17 Correct 1897 ms 65896 KB Output is correct