Submission #155820

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
155820	2019-09-30T16:36:01 Z	m1sch3f	Regions (IOI09_regions)	C++17	100 / 100	5316 ms	94052 KB

regions

#include <bits/stdc++.h>
using namespace std;

// types - only for stuff used a lot 
using ll = long long;
#define vv vector
#define Pp pair

// IO
#define get(x) scanf("%d",&x)
#define getl(x) scanf("%lld",&x);

// Operations
#define pb push_back
#define pob pop_back
#define sz(a) int(a.size()) 
#define re(a,b) a=max(a,b) // relax
#define ri(a,b) a=min(a,b) // relaxi

// Debugging

#ifndef LOCAL
#define cerr if (0) cerr
#else
#define cerr cout
#endif

#define print(arr,n) {for (int _ = 0; _ < n; _++) cerr<<arr[_]<<" "; cerr << endl; }
#define printv(vec)  {for (int _ : vec) cerr<<_<<" "; cerr<<endl;}

const int mod = 1e9+7, oo = 1e9;
const ll loo = 1e18;

// Functions 
ll modpow(ll a, ll b) {
	ll ans = 1; // faster modpow than recursive
	for (; b; b/=2,a=a*a%mod)
		if (b&1) ans = (ans*a)%mod;
	return ans;
}
ll gcd(ll a, ll b) {
	while (a) b%=a,swap(a,b);
	return b;
}
#define bitcount __builtin_popcountll
#define f(i,a,b) for (int i = a; i < b; i++)
#define fr(i,a,b) for (int i = b-1; i >= a; i--)


/* 

   ALRIGHT HACKERS, THIS IS WHERE THE ACTUAL CODE BEGINS

 */

const bool DEBUG = 1;

using pii = pair<int,int>;
using vi = vector<int>;

const int N = 200000, R = 25000;
int C = 500;
int n,r,q;
int h[N], s[N], cnt[R];
map<int,ll> F[R];
vector<pii> points;
vector<pii> atpoints[R];
vi adj[N];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
#ifdef LOCAL
	if (DEBUG) freopen("input.txt", "r", stdin);
	if (DEBUG) freopen("output.txt", "w", stdout);
	clock_t start = clock();
#endif

	cin>>n>>r>>q;
	f(i,0,n) {
		if (i) {
			cin>>s[i]; s[i]--;
			adj[i].pb(s[i]);
			adj[s[i]].pb(i);
		}
		cin>>h[i]; h[i]--;
	}
	fill(cnt,cnt+R,0);
	f(i,0,n) cnt[h[i]]++;
	int t = 0;
	function<void(int,int)> dfs = [&](int v, int p) {
		points.pb({h[v],1});
		atpoints[h[v]].pb({t++,1});
		for (int w : adj[v]) if (w != p)
			dfs(w,v);
		atpoints[h[v]].pb({t++,-1});
		points.pb({h[v],-1});
	};
	dfs(0,-1);
	// there are O(C) of these
	f(c,0,R) if (cnt[c] >= C) {
		int num = 0;
		for (pii pp : points) {
			if (pp == pii(c,1))	
				num++;
			else if (pp == pii(c,-1))
				num--;
			else if (pp.second == 1) 
				F[c][pp.first] += num;
		}			
		// there are C points or more
		num = cnt[c];
		for (pii pp : points) { 
			if (pp.first == c) {
				if (pp.second == 1) num--;
			} else F[pp.first][c] += num*pp.second;
		}
	}
	// rn, all the ones have size C have double the actual value
	f(c,0,R) if (cnt[c] >= C) for (pair<int,ll> pp : F[c]) if (cnt[pp.first] >= C)
		F[c][pp.first] /= 2;
	f(_,0,q) {
		int r1, r2;
		cin>>r1>>r2;
		r1--; r2--;
		if (!F[r1].count(r2)) {
			int c = 0;
			int i = 0, j = 0;
			F[r1][r2] = 0;
			while (j<atpoints[r2].size()) {
				if (i==atpoints[r1].size() || 
					atpoints[r1][i].first > atpoints[r2][j].first) {
					if (atpoints[r2][j++].second == 1)
						F[r1][r2] += c;
				} else c += atpoints[r1][i++].second;	
			}
		}
		cout << F[r1][r2] << endl;
		fflush(stdout);
	}


#ifdef LOCAL
	cout << setprecision(12) << (long double)(clock()-start) / CLOCKS_PER_SEC << endl;
#endif
	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:132:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (j<atpoints[r2].size()) {
           ~^~~~~~~~~~~~~~~~~~~~
regions.cpp:133:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (i==atpoints[r1].size() || 
         ~^~~~~~~~~~~~~~~~~~~~~

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	6776 KB	Output is correct
2	Correct	8 ms	6904 KB	Output is correct
3	Correct	10 ms	6904 KB	Output is correct
4	Correct	20 ms	6904 KB	Output is correct
5	Correct	12 ms	6956 KB	Output is correct
6	Correct	33 ms	7108 KB	Output is correct
7	Correct	41 ms	7260 KB	Output is correct
8	Correct	42 ms	7256 KB	Output is correct
9	Correct	43 ms	8040 KB	Output is correct
10	Correct	98 ms	8100 KB	Output is correct
11	Correct	171 ms	8660 KB	Output is correct
12	Correct	197 ms	9556 KB	Output is correct
13	Correct	207 ms	9584 KB	Output is correct
14	Correct	279 ms	10156 KB	Output is correct
15	Correct	373 ms	14748 KB	Output is correct

Subtask #2

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1221 ms	15624 KB	Output is correct
2	Correct	1321 ms	15112 KB	Output is correct
3	Correct	2235 ms	21108 KB	Output is correct
4	Correct	364 ms	11064 KB	Output is correct
5	Correct	383 ms	14268 KB	Output is correct
6	Correct	915 ms	27784 KB	Output is correct
7	Correct	916 ms	14068 KB	Output is correct
8	Correct	1205 ms	28556 KB	Output is correct
9	Correct	2617 ms	28984 KB	Output is correct
10	Correct	3893 ms	38068 KB	Output is correct
11	Correct	4134 ms	34928 KB	Output is correct
12	Correct	1393 ms	27556 KB	Output is correct
13	Correct	2037 ms	30628 KB	Output is correct
14	Correct	3880 ms	74244 KB	Output is correct
15	Correct	3507 ms	42420 KB	Output is correct
16	Correct	3389 ms	52224 KB	Output is correct
17	Correct	5316 ms	94052 KB	Output is correct