Submission #1140251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140251		raphaelp	Regions (IOI09_regions)	C++20	55 / 100	8051 ms	32036 KiB

regions

#include <bits/stdc++.h>
using namespace std;
#define LSOne(S) ((S) & (-S))
class Fenwick
{
private:
    vector<int> ft;

public:
    Fenwick(int x) { ft.assign(x + 1, 0); }
    int PQ(int x)
    {
        x++;
        int sum = 0;
        for (; x < ft.size(); x += LSOne(x))
            sum += ft[x];
        return sum;
    }
    void update(int a, int b, int val)
    {
        for (; a; a -= LSOne(a))
            ft[a] -= val;
        for (; b; b -= LSOne(b))
            ft[b] += val;
    }
};
void dfs(int x, vector<vector<int>> &AR, vector<int> &deb, vector<int> &fin, int &cur)
{
    deb[x] = cur++;
    for (auto fils : AR[x])
    {
        dfs(fils, AR, deb, fin, cur);
    }
    fin[x] = cur;
}
int main()
{
    int N, R, Q;
    cin >> N >> R >> Q;
    vector<int> p(N), reg(N);
    vector<vector<int>> AR(N), Habs(R);
    for (int i = 0; i < N; i++)
    {
        if (i > 0)
        {
            cin >> p[i];
            p[i]--;
            AR[p[i]].push_back(i);
        }
        cin >> reg[i];
        reg[i]--;
        Habs[reg[i]].push_back(i);
    }
    Fenwick FT(N);
    vector<int> deb(N), fin(N);
    int cur = 0;
    dfs(0, AR, deb, fin, cur);
    for (int i = 0; i < Q; i++)
    {
        int r1, r2;
        cin >> r1 >> r2;
        r1--, r2--;
        int ans = 0;
        for (auto j : Habs[r1])
            FT.update(deb[j], fin[j], 1);
        for (auto j : Habs[r2])
            ans += FT.PQ(deb[j]);
        for (auto j : Habs[r1])
            FT.update(deb[j], fin[j], -1);
        cout << ans << endl;
    }
}

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