oj.uz

Submission #445997

# Submission time Handle Problem Language Result Execution time Memory
445997 2021-07-20T11:46:13 Z grt Specijacija (COCI20_specijacija) C++17
110 / 110
 3928 ms 238956 KB 
#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back

using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 400 * 1000 + 10;
int n, q, t;
ll seq[nax];
int R;
vector<pi>T[(1 << 19)];
vector<pair<ll,int>>val[nax];
map<ll, int>sc;
ll starting[nax]; 
vi V[nax*2];

int f(int k) {
	int v = 1;
	while(v < R) {
		if(T[2*v].back().ST >= k) {
			v = v * 2;
		} else {
			k -= T[2 * v].back().ST;
			v = v * 2 + 1;
		}
	}
	return v - R;
}

inline int g(vector<pi>&vec, int ti) {
	int low = 0, high = (int)vec.size() - 1, mid;
	while(low <= high) {
		mid = (low + high) >> 1;
		if(vec[mid].ND >= ti) {
			low = mid + 1;
		} else {
			high = mid - 1;
		}
	}
	return low - 1;
}

int f2(int k, int ti) {
	int v = 1;
	while(v < R) {
		if(T[2*v][g(T[2*v], ti)].ST >= k) {
			v = v * 2;
		} else {
			k -= T[2*v][g(T[2 * v], ti)].ST;
			v = v * 2 + 1;
		}
	}
	return v - R;
}

void add(int a, int x, int ti) {
	a += R;
	T[a].PB({T[a].back().ST + x, ti});
	while(a > 1) {
		a /= 2;
		T[a].PB({T[a].back().ST + x, ti});
	}
}

int par[nax * 2][19], dp[nax * 2];
ll inv[nax * 2];
 
inline void dfs(int x) {
	for(int nbh : V[x]) {
		dp[nbh] = dp[x] + 1;
		dfs(nbh);
		par[nbh][0] = x;
	}
}
 
inline int lca(int a, int b) {
	if(dp[a] < dp[b]) swap(a, b);
	for(int i = 18; i >= 0; --i) {
		if(dp[par[a][i]] >= dp[b]) {
			a = par[a][i];
		}
	}
	if(a == b) return -a;
	for(int i = 18; i >= 0; --i) {
		if(par[a][i] != par[b][i]) {
			a = par[a][i];
			b = par[b][i];
		}
	}
	return par[a][0];
}

ll ustal(ll x) {
	int low = 1, high = n + 1, mid;
	while(low <= high) {
		mid = (low + high) >> 1;
		if(starting[mid] <= x) {
			low = mid + 1;
		} else {
			high = mid - 1;
		}
	}
	low--;
	int k = x - starting[low] + 1;
	int dep = low;
	int pos = f2(k, dep);
	low = 0; high = (int)val[pos].size() - 1;
	while(low <= high) {
		mid = (low + high) / 2;
		if(val[pos][mid].ND >= dep) {
			low = mid + 1;
		} else {
			high = mid - 1;
		}
	}
	return val[pos][low - 1].ST;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q >> t;
	ll start = 1;
	R = 1;
	while(R <= n + 1) R *= 2;
	for(int i = 1; i <= n; ++i) {
		starting[i] = start;
		cin >> seq[i];
		sc[seq[i]];
		start += i;
	}
	starting[n + 1] = start;
	for(int i = 1; i < 2 * R; ++i) T[i].PB({0, n + 2});
	for(int i = 1; i <= n + 1; ++i) {
		sc[start + i - 1];
		val[i].PB({start + i - 1, n + 1});
		add(i, 1, n + 1);
	}
	int nr = 1;
	for(auto &it : sc) {
		inv[nr] = it.ST;
		it.ND = nr++;
	}
	for(int step = n; step >= 1; --step) {
		int k = seq[step] + step + 1 - start;
		int pos = f(k), pos2 = f(k + 1);
		add(pos2, -1, step);
		V[sc[seq[step]]].PB(sc[val[pos].back().ST]);
		V[sc[seq[step]]].PB(sc[val[pos2].back().ST]);
		val[pos].PB({seq[step], step});
		start -= step;
	}
	
	ll ans = 0;
	dp[1] = 1;
	dfs(sc[1]);
	for(int s = 1; s <= 18; ++s) {
		for(int i = 1; i <= nr; ++i) {
			par[i][s] = par[par[i][s - 1]][s - 1];
		}
	}
	while(q--) {
		ll x, y;
		cin >> x >> y;
		x = ((x - 1 + t * ans)%((ll)(n+1)*(n+2)/2)) + 1;
		y = ((y - 1 + t * ans)%((ll)(n+1)*(n+2)/2)) + 1;
		ll xa = ustal(x);
		ll ya = ustal(y);
		//cout << xa << " " << ya << "\n";
		if(xa == ya) {
			cout << min(x, y) << "\n";
			ans = min(x, y);
			continue;
		}
		int l = lca(sc[xa], sc[ya]);
		//cout << l << "\n";
		if(l < 0) {
			cout << min(x, y) << "\n";
			ans = min(x, y);
			continue;
		}
		cout << inv[l] << "\n";
		ans = inv[l];
	}
	
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1417 ms 232672 KB Output is correct
2 Correct 88 ms 57400 KB Output is correct
3 Correct 1406 ms 234004 KB Output is correct
4 Correct 687 ms 142296 KB Output is correct
5 Correct 1427 ms 233144 KB Output is correct
6 Correct 381 ms 98728 KB Output is correct
7 Correct 926 ms 231404 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1417 ms 232672 KB Output is correct
2 Correct 88 ms 57400 KB Output is correct
3 Correct 1406 ms 234004 KB Output is correct
4 Correct 687 ms 142296 KB Output is correct
5 Correct 1427 ms 233144 KB Output is correct
6 Correct 381 ms 98728 KB Output is correct
7 Correct 926 ms 231404 KB Output is correct
8 Correct 442 ms 44680 KB Output is correct
9 Correct 382 ms 44000 KB Output is correct
10 Correct 453 ms 44720 KB Output is correct
11 Correct 251 ms 43192 KB Output is correct
12 Correct 436 ms 44696 KB Output is correct
13 Correct 299 ms 43588 KB Output is correct
14 Correct 375 ms 45192 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1417 ms 232672 KB Output is correct
2 Correct 88 ms 57400 KB Output is correct
3 Correct 1406 ms 234004 KB Output is correct
4 Correct 687 ms 142296 KB Output is correct
5 Correct 1427 ms 233144 KB Output is correct
6 Correct 381 ms 98728 KB Output is correct
7 Correct 926 ms 231404 KB Output is correct
8 Correct 442 ms 44680 KB Output is correct
9 Correct 382 ms 44000 KB Output is correct
10 Correct 453 ms 44720 KB Output is correct
11 Correct 251 ms 43192 KB Output is correct
12 Correct 436 ms 44696 KB Output is correct
13 Correct 299 ms 43588 KB Output is correct
14 Correct 375 ms 45192 KB Output is correct
15 Correct 3921 ms 238468 KB Output is correct
16 Correct 1661 ms 84708 KB Output is correct
17 Correct 3928 ms 238956 KB Output is correct
18 Correct 1716 ms 85804 KB Output is correct
19 Correct 3854 ms 237980 KB Output is correct
20 Correct 1579 ms 81376 KB Output is correct
21 Correct 2962 ms 237960 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3841 ms 237900 KB Output is correct
2 Correct 2474 ms 137584 KB Output is correct
3 Correct 3835 ms 238508 KB Output is correct
4 Correct 2421 ms 134856 KB Output is correct
5 Correct 3863 ms 238256 KB Output is correct
6 Correct 2559 ms 145368 KB Output is correct
7 Correct 2942 ms 238152 KB Output is correct