Submission #648798

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
648798	2022-10-08T10:35:26 Z	ymm	Regions (IOI09_regions)	C++17	50 / 100	8000 ms	131072 KB

regions

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int S = 256;
const int N = 400'032 + S;
const int R = 25'010;
int reg[N];
int len = 0;
int exp_reg[N];
int delta[N];
vector<int> bl_regs[N/S];
int cnt[N/S][S+1];
int scnt[N/S][S+1];
short sum[N/S][S+1][S+1];
vector<int> A[N];
int n, r, q;

void dfs(int v)
{
	exp_reg[len] = reg[v];
	delta[len] = 1;
	++len;
	for (int u : A[v])
		dfs(u);
	exp_reg[len] = reg[v];
	delta[len] = -1;
	++len;
}

int compress(int i, int x)
{
	auto it = lower_bound(bl_regs[i].begin(), bl_regs[i].end(), x);
	if (it == bl_regs[i].end() || *it != x)
		return S;
	return it - bl_regs[i].begin();
}

void calc_block(int bl)
{
	int l = bl*S, r = min(bl*S+S, len);
	int ans[S][S] = {}, pre[S] = {};
	Loop (i,l,r) {
		int reg = compress(bl, exp_reg[i]);
		Loop (j,0,S)
			ans[reg][j] += pre[j];
		pre[reg] += delta[i];
	}
	Loop (i,0,S) Loop (j,0,S)
		sum[bl][i][j] = ans[j][i];
}

void comp_block(int bl)
{
	int l = bl*S, r = min(bl*S+S, len);
	Loop (i,l,r)
		bl_regs[bl].push_back(exp_reg[i]);
	sort(bl_regs[bl].begin(), bl_regs[bl].end());
	bl_regs[bl].resize(  unique(bl_regs[bl].begin(), bl_regs[bl].end())
	                   - bl_regs[bl].begin());
}

void init()
{
	for (int l = 0; l < len; l += S)
	{
		int r = min(len, l + S);
		comp_block(l/S);
		calc_block(l/S);
		Loop (i,l,r) {
			 cnt[l/S][compress(l/S, exp_reg[i])]++;
			scnt[l/S][compress(l/S, exp_reg[i])] += delta[i];
		}
	}
}

int solve(int r1, int r2)
{
	int ans = 0, pre = 0;
	Loop (i,0,(len+S-1)/S) {
		int cr1 = compress(i, r1);
		int cr2 = compress(i, r2);
		ans += pre * cnt[i][cr2];
		ans += sum[i][cr1][cr2];
		pre += scnt[i][cr1];
	}
	return ans/2;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> r >> q;
	cin >> reg[0];
	Loop (i,1,n) {
		int p;
		cin >> p >> reg[i];
		A[p-1].push_back(i);
	}
	dfs(0);
	init();
	while (q--) {
		int r1, r2;
		cin >> r1 >> r2;
		cout << solve(r1, r2) << '\n';
		cout.flush();
	}
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	10132 KB	Output is correct
2	Correct	6 ms	10064 KB	Output is correct
3	Correct	8 ms	10064 KB	Output is correct
4	Correct	11 ms	10244 KB	Output is correct
5	Correct	13 ms	10604 KB	Output is correct
6	Correct	29 ms	10960 KB	Output is correct
7	Correct	35 ms	11600 KB	Output is correct
8	Correct	44 ms	12240 KB	Output is correct
9	Correct	85 ms	15636 KB	Output is correct
10	Correct	159 ms	20952 KB	Output is correct
11	Correct	245 ms	26352 KB	Output is correct
12	Correct	342 ms	31912 KB	Output is correct
13	Correct	403 ms	35656 KB	Output is correct
14	Correct	531 ms	42484 KB	Output is correct
15	Correct	834 ms	55608 KB	Output is correct

Subtask #2

35.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5207 ms	91848 KB	Output is correct
2	Correct	6121 ms	95760 KB	Output is correct
3	Execution timed out	8023 ms	109544 KB	Time limit exceeded
4	Correct	863 ms	42436 KB	Output is correct
5	Correct	1305 ms	51604 KB	Output is correct
6	Correct	2626 ms	66248 KB	Output is correct
7	Correct	5582 ms	85504 KB	Output is correct
8	Correct	7634 ms	122632 KB	Output is correct
9	Runtime error	242 ms	131072 KB	Execution killed with signal 9
10	Runtime error	219 ms	131072 KB	Execution killed with signal 9
11	Runtime error	239 ms	131072 KB	Execution killed with signal 9
12	Runtime error	277 ms	131072 KB	Execution killed with signal 9
13	Runtime error	235 ms	131072 KB	Execution killed with signal 9
14	Runtime error	284 ms	131072 KB	Execution killed with signal 9
15	Runtime error	213 ms	131072 KB	Execution killed with signal 9
16	Runtime error	212 ms	131072 KB	Execution killed with signal 9
17	Runtime error	256 ms	131072 KB	Execution killed with signal 9