oj.uz

Submission #525645

# Submission time Handle Problem Language Result Execution time Memory
525645 2022-02-12T08:50:16 Z Aldas25 Regions (IOI09_regions) C++14
100 / 100
 3807 ms 34348 KB 
#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(0)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 250100, MAXK = 20;
const ll MOD = 1e9+7;

const ll C = 500;
const ll c = 500;

int n, r, q;
int h[MAXN];
int regSz[MAXN];
bool bgReg[MAXN];
vi adj[MAXN];

int regToId[MAXN];
int idToReg[MAXN];

int tin[MAXN], tout[MAXN];
int crT = 0;

void dfs (int v, int p = -1) {
    tin[v] = ++crT;

    for (int u : adj[v]) {
        dfs (u, v);
    }

    tout[v] = crT;
}

bool isAnc (int a, int b) {
    return (tin[a] <= tin[b] && tout[b] <= tout[a]);
}

vii nodes;
vii inReg[MAXN];
ll pref[MAXN];
ll ans[C][25100];

int getUpperBound (int r, int x) {
    int sz = (int)inReg[r].size();
    if (sz == 0) return sz;
    if (inReg[r][sz-1].f <= x) return sz;

    int le = 0, ri = sz-1;
    while (le < ri) {
        int m = (le+ri)/2;
        if (inReg[r][m].f > x) ri = m;
        else le = m+1;
    }

    return le;
}

int main()
{
    FAST_IO;

    cin >> n >> r >> q;
    cin >> h[1];
    FOR(i, 2, n) {
        int pr; cin >> pr;
        adj[pr].pb(i);
        cin >> h[i];

    }

    FOR(i, 1, n) regSz[h[i]]++;
    int lstId = 0;
    FOR(i, 1, r) {
        bgReg[i] = (regSz[i] > c);

        if (bgReg[i]) {
            regToId[i] = ++lstId;
            idToReg[lstId] = i;
        }

       // cout << " i = " << i << " regSz = " << regSz[i] << " bg = " << bgReg[i] << endl;
       // if (bgReg[i]) cout << "     regToId[i]=" << regToId[i] << endl;
    }

    dfs(1);

    FOR(i, 1, n) {
        nodes.pb({tin[i], i});
        inReg[h[i]].pb({tin[i], i});
    }

    sort(nodes.begin(), nodes.end());
    FOR(i, 1, r) sort(inReg[i].begin(), inReg[i].end());

    FOR(i, 0, C-1) {
        if (idToReg[i] == 0) continue;
        int r = idToReg[i];

        FOR(j, 0, n) pref[j] = 0;
        for (auto p : inReg[r]) {
            int v = p.s;
            pref[tin[v]]++;
            pref[tout[v]+1]--;
        }
        FOR(j, 1, n) pref[j] += pref[j-1];

        FOR(j, 1, n) {
            int v = nodes[j-1].s;
            ans[i][h[v]] += pref[j];
        }

    }

    REP(q) {
        int r1, r2;
        cin >> r1 >> r2;

        if (bgReg[r1]) {
            cout << ans[regToId[r1]][r2] << endl;
        } else {
            ll ats = 0;
            for (auto p : inReg[r1]) {
                int v = p.s;

                int ri = getUpperBound (r2, tout[v]);
                int le = getUpperBound (r2, tin[v]);

                ats += max(0, ri-le);
            }

            cout << ats << endl;
        }
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11976 KB Output is correct
2 Correct 7 ms 11976 KB Output is correct
3 Correct 8 ms 12104 KB Output is correct
4 Correct 14 ms 12104 KB Output is correct
5 Correct 15 ms 12112 KB Output is correct
6 Correct 26 ms 12104 KB Output is correct
7 Correct 35 ms 12104 KB Output is correct
8 Correct 39 ms 12232 KB Output is correct
9 Correct 54 ms 12488 KB Output is correct
10 Correct 101 ms 12688 KB Output is correct
11 Correct 128 ms 13000 KB Output is correct
12 Correct 165 ms 13576 KB Output is correct
13 Correct 157 ms 13348 KB Output is correct
14 Correct 283 ms 13988 KB Output is correct
15 Correct 284 ms 15812 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1915 ms 17696 KB Output is correct
2 Correct 2035 ms 16820 KB Output is correct
3 Correct 2220 ms 19340 KB Output is correct
4 Correct 294 ms 13960 KB Output is correct
5 Correct 370 ms 15312 KB Output is correct
6 Correct 1165 ms 15172 KB Output is correct
7 Correct 1490 ms 16832 KB Output is correct
8 Correct 1214 ms 20108 KB Output is correct
9 Correct 1773 ms 22688 KB Output is correct
10 Correct 3807 ms 25960 KB Output is correct
11 Correct 3753 ms 22320 KB Output is correct
12 Correct 1280 ms 25700 KB Output is correct
13 Correct 1781 ms 25500 KB Output is correct
14 Correct 1995 ms 29104 KB Output is correct
15 Correct 2910 ms 28716 KB Output is correct
16 Correct 2905 ms 31372 KB Output is correct
17 Correct 2930 ms 34348 KB Output is correct