oj.uz

Submission #516539

# Submission time Handle Problem Language Result Execution time Memory
516539 2022-01-21T12:56:08 Z blue Regions (IOI09_regions) C++17
100 / 100
 2736 ms 65848 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 = 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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 32856 KB Output is correct
2 Correct 14 ms 32904 KB Output is correct
3 Correct 15 ms 32924 KB Output is correct
4 Correct 18 ms 32900 KB Output is correct
5 Correct 21 ms 32940 KB Output is correct
6 Correct 46 ms 33048 KB Output is correct
7 Correct 31 ms 33156 KB Output is correct
8 Correct 30 ms 33244 KB Output is correct
9 Correct 66 ms 33712 KB Output is correct
10 Correct 67 ms 34512 KB Output is correct
11 Correct 132 ms 35260 KB Output is correct
12 Correct 144 ms 36104 KB Output is correct
13 Correct 175 ms 36764 KB Output is correct
14 Correct 178 ms 37812 KB Output is correct
15 Correct 183 ms 39952 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 44300 KB Output is correct
2 Correct 854 ms 44876 KB Output is correct
3 Correct 1478 ms 46472 KB Output is correct
4 Correct 225 ms 37916 KB Output is correct
5 Correct 230 ms 38840 KB Output is correct
6 Correct 657 ms 41132 KB Output is correct
7 Correct 959 ms 44400 KB Output is correct
8 Correct 825 ms 48664 KB Output is correct
9 Correct 1063 ms 58100 KB Output is correct
10 Correct 2039 ms 60900 KB Output is correct
11 Correct 2459 ms 65420 KB Output is correct
12 Correct 1161 ms 62756 KB Output is correct
13 Correct 1616 ms 62548 KB Output is correct
14 Correct 2106 ms 64684 KB Output is correct
15 Correct 2736 ms 65848 KB Output is correct
16 Correct 2246 ms 65636 KB Output is correct
17 Correct 1857 ms 64688 KB Output is correct