Submission #445997

#	Time	Username	Problem	Language	Result	Execution time	Memory
445997		grt	Specijacija (COCI20_specijacija)	C++17	110 / 110	3928 ms	238956 KiB

Main

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60