oj.uz

Submission #548382

# Submission time Handle Problem Language Result Execution time Memory
548382 2022-04-13T07:55:23 Z Jomnoi Regions (IOI09_regions) C++17
100 / 100
 3726 ms 47804 KB 
#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;

const int MAX_N = 2e5 + 10;
const int MAX_R = 3e4 + 10;;
const int B = 500;

int timer;
int H[MAX_N];
int sz[MAX_N], st[MAX_N], pos[MAX_N];
vector <int> graph[MAX_N];
vector <int> region[MAX_R];
map <int, int> ans[MAX_R];
int pre[MAX_N];

int get_size(const int &u) {
    timer++;
    st[u] = timer;
    pos[timer] = u;
    sz[u] = 1;
    for(auto v : graph[u]) {
        sz[u] += get_size(v);
    }
    return sz[u];
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int N, R, Q;
    cin >> N >> R >> Q;
    for(int i = 1; i <= N; i++) {
        int S;
        if(i != 1) {
            cin >> S;
            graph[S].push_back(i);
        }
        cin >> H[i];
    }

    get_size(1);

    for(int i = 1; i <= N; i++) {
        region[H[i]].push_back(st[i]);
    }
    for(int i = 1; i <= R; i++) {
        sort(region[i].begin(), region[i].end());
    }

    for(int i = 1; i <= R; i++) {
        if(region[i].size() < B) {
            continue;
        }

        fill(pre, pre + N + 1, 0);
        for(auto v : region[i]) {
            pre[v]++;
            pre[v + sz[pos[v]]]--;
        }
        for(int j = 1; j <= N; j++) {
            pre[j] += pre[j - 1];
            ans[H[pos[j]]][i] += pre[j];
        }
    }

    for(int i = 1; i <= Q; i++) {
        int r1, r2;
        cin >> r1 >> r2;
        if(region[r1].size() >= B) {
            cout << ans[r2][r1] << endl;
            continue;
        }

        int res = 0;
        for(auto v : region[r1]) {
            res += upper_bound(region[r2].begin(), region[r2].end(), v + sz[pos[v]] - 1) - lower_bound(region[r2].begin(), region[r2].end(), v);
        }
        cout << res << endl;
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7120 KB Output is correct
2 Correct 4 ms 7120 KB Output is correct
3 Correct 6 ms 7120 KB Output is correct
4 Correct 8 ms 7120 KB Output is correct
5 Correct 11 ms 7120 KB Output is correct
6 Correct 19 ms 7248 KB Output is correct
7 Correct 28 ms 7120 KB Output is correct
8 Correct 37 ms 7248 KB Output is correct
9 Correct 47 ms 7632 KB Output is correct
10 Correct 69 ms 7632 KB Output is correct
11 Correct 105 ms 7888 KB Output is correct
12 Correct 120 ms 8400 KB Output is correct
13 Correct 102 ms 8016 KB Output is correct
14 Correct 259 ms 8680 KB Output is correct
15 Correct 240 ms 11708 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1697 ms 12248 KB Output is correct
2 Correct 1839 ms 10824 KB Output is correct
3 Correct 2433 ms 14448 KB Output is correct
4 Correct 189 ms 8656 KB Output is correct
5 Correct 345 ms 10632 KB Output is correct
6 Correct 851 ms 15648 KB Output is correct
7 Correct 1554 ms 10844 KB Output is correct
8 Correct 1045 ms 18620 KB Output is correct
9 Correct 1751 ms 16200 KB Output is correct
10 Correct 3726 ms 22088 KB Output is correct
11 Correct 3591 ms 15704 KB Output is correct
12 Correct 1412 ms 19432 KB Output is correct
13 Correct 1792 ms 19880 KB Output is correct
14 Correct 2293 ms 35688 KB Output is correct
15 Correct 2746 ms 25548 KB Output is correct
16 Correct 2436 ms 32840 KB Output is correct
17 Correct 2694 ms 47804 KB Output is correct