oj.uz

Submission #155803

# Submission time Handle Problem Language Result Execution time Memory
155803 2019-09-30T15:48:42 Z m1sch3f Regions (IOI09_regions) C++17
60 / 100
 8000 ms 56356 KB 

#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);
	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;
		}			
		// O(N/C*R)
		int freq[R];
		fill(freq,freq+R,0);
		for (pii pp : points) {
			if (pp == pii(c,-1))
				continue;
			if (pp == pii(c,1))
				f(i,0,R) F[i][c] += freq[i];
			else
				freq[pp.first] += pp.second;
		}
	}
	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 6908 KB Output is correct
3 Correct 10 ms 6904 KB Output is correct
4 Correct 12 ms 6904 KB Output is correct
5 Correct 16 ms 7032 KB Output is correct
6 Correct 28 ms 7208 KB Output is correct
7 Correct 39 ms 7160 KB Output is correct
8 Correct 47 ms 7208 KB Output is correct
9 Correct 73 ms 8060 KB Output is correct
10 Correct 103 ms 8216 KB Output is correct
11 Correct 137 ms 8680 KB Output is correct
12 Correct 127 ms 9564 KB Output is correct
13 Correct 171 ms 9608 KB Output is correct
14 Correct 173 ms 10124 KB Output is correct
15 Correct 329 ms 14764 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8007 ms 26520 KB Time limit exceeded
2 Execution timed out 8077 ms 24240 KB Time limit exceeded
3 Execution timed out 8010 ms 26396 KB Time limit exceeded
4 Correct 285 ms 11016 KB Output is correct
5 Correct 476 ms 14288 KB Output is correct
6 Execution timed out 8045 ms 48760 KB Time limit exceeded
7 Correct 846 ms 14156 KB Output is correct
8 Correct 1686 ms 31560 KB Output is correct
9 Correct 2445 ms 29172 KB Output is correct
10 Correct 3976 ms 38184 KB Output is correct
11 Correct 3883 ms 34984 KB Output is correct
12 Correct 7479 ms 29000 KB Output is correct
13 Correct 7947 ms 32108 KB Output is correct
14 Execution timed out 8069 ms 41456 KB Time limit exceeded
15 Execution timed out 8034 ms 37708 KB Time limit exceeded
16 Execution timed out 8013 ms 50156 KB Time limit exceeded
17 Execution timed out 8028 ms 56356 KB Time limit exceeded