oj.uz

Submission #516536

# Submission time Handle Problem Language Result Execution time Memory
516536 2022-01-21T12:54:22 Z blue Regions (IOI09_regions) C++17
0 / 100
 2349 ms 66412 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];
    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])
        {
            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-1;
            }

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

        cout.flush();
    }

    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 32900 KB Output isn't correct
2 Incorrect 13 ms 32884 KB Output isn't correct
3 Incorrect 16 ms 32856 KB Output isn't correct
4 Incorrect 18 ms 32964 KB Output isn't correct
5 Incorrect 21 ms 33008 KB Output isn't correct
6 Incorrect 35 ms 33028 KB Output isn't correct
7 Incorrect 47 ms 33156 KB Output isn't correct
8 Incorrect 50 ms 33192 KB Output isn't correct
9 Incorrect 61 ms 33796 KB Output isn't correct
10 Incorrect 89 ms 34504 KB Output isn't correct
11 Incorrect 101 ms 35144 KB Output isn't correct
12 Incorrect 129 ms 36156 KB Output isn't correct
13 Incorrect 134 ms 36872 KB Output isn't correct
14 Incorrect 169 ms 37804 KB Output isn't correct
15 Incorrect 195 ms 40052 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 828 ms 44616 KB Output isn't correct
2 Incorrect 996 ms 45296 KB Output isn't correct
3 Incorrect 1380 ms 46916 KB Output isn't correct
4 Incorrect 199 ms 37920 KB Output isn't correct
5 Incorrect 309 ms 38848 KB Output isn't correct
6 Incorrect 721 ms 41212 KB Output isn't correct
7 Incorrect 857 ms 44400 KB Output isn't correct
8 Incorrect 1111 ms 48676 KB Output isn't correct
9 Incorrect 1743 ms 58028 KB Output isn't correct
10 Incorrect 2024 ms 60724 KB Output isn't correct
11 Incorrect 2265 ms 65412 KB Output isn't correct
12 Incorrect 1091 ms 63264 KB Output isn't correct
13 Incorrect 1408 ms 63016 KB Output isn't correct
14 Incorrect 1630 ms 65416 KB Output isn't correct
15 Incorrect 2129 ms 66412 KB Output isn't correct
16 Incorrect 1910 ms 66316 KB Output isn't correct
17 Incorrect 2349 ms 65604 KB Output isn't correct