oj.uz

Submission #516502

# Submission time Handle Problem Language Result Execution time Memory
516502 2022-01-21T12:31:22 Z blue Regions (IOI09_regions) C++17
90 / 100
 2491 ms 89772 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 = 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];
    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 22 ms 37652 KB Output is correct
2 Correct 20 ms 37640 KB Output is correct
3 Correct 22 ms 37640 KB Output is correct
4 Correct 24 ms 37636 KB Output is correct
5 Correct 23 ms 37708 KB Output is correct
6 Correct 34 ms 37752 KB Output is correct
7 Correct 43 ms 37820 KB Output is correct
8 Correct 70 ms 37916 KB Output is correct
9 Correct 46 ms 38508 KB Output is correct
10 Correct 99 ms 39200 KB Output is correct
11 Correct 117 ms 39972 KB Output is correct
12 Correct 181 ms 40832 KB Output is correct
13 Correct 160 ms 41340 KB Output is correct
14 Correct 282 ms 42516 KB Output is correct
15 Correct 237 ms 44616 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1032 ms 49012 KB Output is correct
2 Correct 1041 ms 49584 KB Output is correct
3 Correct 1711 ms 51188 KB Output is correct
4 Correct 257 ms 42632 KB Output is correct
5 Correct 435 ms 43552 KB Output is correct
6 Correct 586 ms 45824 KB Output is correct
7 Correct 1045 ms 49108 KB Output is correct
8 Runtime error 93 ms 83852 KB Execution killed with signal 11
9 Correct 1394 ms 62744 KB Output is correct
10 Runtime error 123 ms 89772 KB Execution killed with signal 11
11 Correct 2491 ms 70140 KB Output is correct
12 Correct 973 ms 67432 KB Output is correct
13 Correct 1337 ms 67252 KB Output is correct
14 Correct 1416 ms 69400 KB Output is correct
15 Correct 2142 ms 70532 KB Output is correct
16 Correct 2359 ms 70320 KB Output is correct
17 Correct 2381 ms 69412 KB Output is correct