제출 #1136232

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1136232		farica	Regions (IOI09_regions)	C++20	0 / 100	29 ms	17212 KiB

regions

#include <bits/stdc++.h>
#define int long long

using namespace std;
using vi = vector<int>;
using pi = pair<int,int>;
using ll = long long;

const int N = 2e5 + 5;
const int REG = 25005;
const int INF = 1e9;
const int B = sqrt(N);

vector<vi>adjL(N);
vector<vector<pi>>R(REG), queries(REG);
vi reg(N), p(N), tmp, tmp2, tmp3;
int cnt;

void build(int pos) {
    R[reg[pos]].push_back({cnt++, 1});
    for(int adj: adjL[pos]) build(adj);
    R[reg[pos]].push_back({cnt++, -1});
}

void dfs(int pos, int col) {
    if(tmp3[pos] != -1) ++tmp2[tmp3[pos]];
    if(reg[pos] == col) {
        for(pi x: queries[col]) tmp[tmp3[x.first]] += tmp2[tmp3[x.first]];
    }
    for(int adj: adjL[pos]) dfs(adj, col);
    if(tmp3[pos] != -1) --tmp2[tmp3[pos]];
}

void solve() {
    int n, r, q;
    cin >> n >> r >> q;
    for(int i=0; i<n; ++i) {
        if(!i) cin >> reg[i];
        else cin >> p[i] >> reg[i];
        --reg[i], --p[i];
        if(i) adjL[p[i]].push_back(i);
    }
    vi ans(q, 0);
    for(int i=0; i<q; ++i) {
        int r1, r2;
        cin >> r1 >> r2;
        --r1, --r2;
        queries[r2].push_back({r1, i});
    }
    build(0);
    tmp.assign(r, 0);
    tmp2.assign(r, 0);
    tmp3.assign(r, -1);
    vector<vi>pref(r);
    for(int i=0; i<r; ++i) {
        for(pi p: R[i]) {
            int cur = 0;
            if(!pref[i].empty()) cur = pref[i].back();
            pref[i].push_back(cur + p.second);
        }
    }
    for(int i=0; i<r; ++i) {
        int siz = (int)R[i].size();
        siz /= 2;
        if(siz > B) {
            for(int j=0; j<queries[i].size(); ++j) tmp3[queries[i][j].first] = j;
            dfs(0, i);
            for(int j=0; j<queries[i].size(); ++j) {
                ans[queries[i][j].second] = tmp[j];
                tmp3[queries[i][j].first] = -1;
            }
        } else {
            for(pi p: R[i]) {
                if(p.second == -1) continue;
                for(pi x: queries[i]) {
                    pi Tmp = {p.first, -2};
                    int pos = upper_bound(R[x.first].begin(), R[x.first].end(), Tmp) - R[x.first].begin();
                    if(pos) ans[x.second] += pref[x.first][pos-1];
                }
            }
        }
    }
    for(int i=0; i<q; ++i) cout << ans[i] << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t = 1;
    while(t--) solve();

    return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 85