Submission #477499

#	Time	Username	Problem	Language	Result	Execution time	Memory
477499		Abrar_Al_Samit	Regions (IOI09_regions)	C++17	0 / 100	2310 ms	59068 KiB

regions

#include<bits/stdc++.h>
using namespace std;
const int MX = 200005;
struct FenwickTree {
    vector<int> bit;  // binary indexed tree
    int n = MX;

    int sum(int r) {
    	if(bit.empty()) bit.resize(n);
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }

    int sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }

    void add(int idx, int delta) {
    	if(bit.empty()) bit.resize(n);
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};
const int B = 500;
int N, R, Q;
vector <int> g[MX], regionAll[MX], regionEl[MX];
int H[MX], st[MX], en[MX], timer=1;
int found[MX];
map <int, vector <int>> prep;
void Flat(int v, int p) {
	st[v] = timer++;
	if(!found[H[v]]) {
		found[H[v]] = st[v];
		regionEl[H[v]].push_back(v);
	}
	regionAll[H[v]].push_back(v);
	for(auto to : g[v]) if(to!=p) {
		Flat(to, v);
	}
	en[v] = timer-1;
	if(found[H[v]]==st[v]) {
		found[H[v]] = 0;
	}
}
int main() {
	cin >> N >> R >> Q;
	cin >> H[1];
	for(int i=2; i<=N; ++i) {
		int p; cin >> p >> H[i];
		g[p].push_back(i);
	}
	Flat(1, 1);
	vector <int> bigs;
	for(int i=1; i<=R; ++i) if(regionAll[i].size()>B) {
		bigs.push_back(i);
	}
	int sz_big = bigs.size();
	FenwickTree A;
	for(int all=1; all<=25000; ++all) {
		for(auto it : regionAll[all]) {
			A.add(st[it], 1);
		}
		for(auto b : bigs) {
			if(prep[b].empty()) prep[b].resize(25001);
			for(auto it : regionEl[b]) {
				prep[b][all] = A.sum(st[it], en[it]);
			}
		}
		for(auto it : regionAll[all]) {
			A.add(st[it], -1);
		}
	}
	map <int, FenwickTree> sb;
	for(auto b : bigs) {
		for(auto it : regionAll[b]) {
			sb[b].add(st[it], 1);
		}
	}
	while(Q--) {
		int r1, r2;
		cin >> r1 >> r2;
		int ans = 0;
		if(regionAll[r1].size()>B) {
			ans = prep[r1][r2];
		} else {
			if(regionAll[r2].size()>B) {
				for(auto it : regionEl[r1]) {
					ans += sb[r2].sum(st[it], en[it]);
				}
			} else {
				int p1 = 0, p2 = 0;
				while(p1<regionEl[r1].size() && p2<regionAll[r2].size()) {
					auto ok = [&] (int p1, int p2) {
						return st[regionEl[r1][p1]]<=st[regionAll[r2][p2]] &&
						en[regionEl[r1][p1]]>=en[regionAll[r2][p2]];
					};
					while(p2<regionAll[r2].size() && ok(p1, p2)) ++p2, ++ans;
					while(p2<regionAll[r2].size() && st[regionAll[r2][p2]]<st[regionEl[r1][p1]]) ++p2;
					if(p2==regionAll[r2].size()) continue;
					while(p1<regionEl[r1].size() && en[regionEl[r1][p1]]<st[regionAll[r2][p2]]) ++p1;
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:94:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     while(p1<regionEl[r1].size() && p2<regionAll[r2].size()) {
      |           ~~^~~~~~~~~~~~~~~~~~~~
regions.cpp:94:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     while(p1<regionEl[r1].size() && p2<regionAll[r2].size()) {
      |                                     ~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:99:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |      while(p2<regionAll[r2].size() && ok(p1, p2)) ++p2, ++ans;
      |            ~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:100:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |      while(p2<regionAll[r2].size() && st[regionAll[r2][p2]]<st[regionEl[r1][p1]]) ++p2;
      |            ~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:101:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |      if(p2==regionAll[r2].size()) continue;
      |         ~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:102:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |      while(p1<regionEl[r1].size() && en[regionEl[r1][p1]]<st[regionAll[r2][p2]]) ++p1;
      |            ~~^~~~~~~~~~~~~~~~~~~~
regions.cpp:59:6: warning: unused variable 'sz_big' [-Wunused-variable]
   59 |  int sz_big = bigs.size();
      |      ^~~~~~

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