oj.uz

Submission #445548

# Submission time Handle Problem Language Result Execution time Memory
445548 2021-07-18T15:49:25 Z grt Specijacija (COCI20_specijacija) C++17
20 / 110
 4000 ms 299856 KB 
#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back
#define int long long

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];

vector<pair<ll, int>>T1[(1 << 19)];
vector<pair<ll, int>>T2[(1 << 19)];
int R;
vi V[nax];
map<ll,int>sc;
ll starting[nax];

void add(int a, int b, int x, int ti) {
	a += R; b += R;
	T1[a].PB({T1[a].back().ST + x, ti});
	if(a != b) T1[b].PB({T1[b].back().ST + x, ti});
	while(a / 2 != b / 2) {
		if(a % 2 == 0) T1[a + 1].PB({T1[a + 1].back().ST + x, ti});
		if(b % 2 == 1) T1[b - 1].PB({T1[b - 1].back().ST + x, ti});
		a /= 2;
		b /= 2;
	}
}

void ustaw(int a, int b, ll x, int ti) {
	a += R; b += R;
	T2[a].PB({x, ti});
	if(a != b) T2[b].PB({x, ti});
	while(a / 2 != b / 2) {
		if(a % 2 == 0) T2[a + 1].PB({x, ti});
		if(b % 2 == 1) T2[b - 1].PB({x, ti});
		a /= 2;
		b /= 2;
	}
}

ll askVal(int x) {
	x += R;
	pair<ll,int> w = T2[x].back();
	while(x > 1) {
		x /= 2;
		if(w.ND > T2[x].back().ND) {
			w = T2[x].back();
		}
	}
	return w.ST;
}

int ask(int x) {
	x += R;
	int w = T1[x].back().ST;
	while(x > 1) {
		x /= 2;
		w += T1[x].back().ST;
	}
	return w;
}

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

ll askVal2(int x, int ti) {
	x += R;
	pair<ll,int>w = g(T2[x], ti);
	while(x > 1) {
		x /= 2;
		pair<ll,int>w2 = g(T2[x], ti);
		if(w2.ND < w.ND) {
			w = w2;
		}
	}
	return w.ST;
}

int ask2(int x, int ti) {
	x += R;
	int w = g(T1[x], ti).ST;
	while(x > 1) {
		x /= 2;
		w += g(T1[x], ti).ST;
	}
	return w;
}

int f(int x) {
	int low = 1, high = n + 1, mid;
	while(low <= high) {
		mid = (low + high) / 2;
		if(ask(mid) >= x) {
			high = mid - 1;
		} else {
			low = mid + 1;
		}
	}
	return high + 1;
}

int f2(int x, int ti) {
	int low = 1, high = n + 1, mid;
	while(low <= high) {
		mid = (low + high) / 2;
		if(ask2(mid, ti) >= x) {
			high = mid - 1;
		} else {
			low = mid + 1;
		}
	}
	return high + 1;
}

ll ustal(ll x) {
	int low = 1, high = n + 1, mid;
	while(low <= high) {
		mid = (low + high) / 2;
		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);
	return askVal2(pos, dep);
}

int par[2*nax][19], dp[2*nax];
ll inv[2 * nax];

void dfs(int x) {
	for(int nbh : V[x]) {
		dp[nbh] = dp[x] + 1;
		dfs(nbh);
		par[nbh][0] = x;
	}
}

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];
}


__int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q >> t;
	ll start = 1;
	for(int i = 1; i <= n; ++i) {
		starting[i] = start;
		cin >> seq[i];
		sc[seq[i]];
		start += i;
	}
	starting[n + 1] = start;
	R = 1;
	while(R <= n + 1) R *= 2;
	for(int i = 1; i < 2 * R; ++i) {
		T1[i].PB({0, n + 2});
		T2[i].PB({0, n + 2});
	}
	for(int i = 1; i <= n + 1; ++i) {
		add(i, i, i, n + 1);
		ustaw(i, i, start + i - 1, n + 1);
		sc[start + i - 1];
	}
	int nr = 1;
	for(auto &it : sc) {
		inv[nr] = it.ST;
		it.ND = nr++;
	}
	for(int i = n; i >= 1; --i) {
		// val = a[i] + i - start + 1
		int val = seq[i] + i - start + 1;
		int pos = f(val + 1);
		int l = f(val), r = f(val + 2) - 1;
		int val1 = askVal(l);
		int val2 = askVal(r);
		V[sc[seq[i]]].PB(sc[val1]);
		V[sc[seq[i]]].PB(sc[val2]);
		ustaw(l, r, seq[i], i);
		add(pos, n + 1, -1, i);
		start -= i;
	}
	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]);
		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 2506 ms 263040 KB Output is correct
2 Correct 152 ms 54820 KB Output is correct
3 Correct 2543 ms 265404 KB Output is correct
4 Correct 1253 ms 163852 KB Output is correct
5 Correct 2533 ms 265288 KB Output is correct
6 Correct 661 ms 108856 KB Output is correct
7 Correct 1478 ms 299856 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2506 ms 263040 KB Output is correct
2 Correct 152 ms 54820 KB Output is correct
3 Correct 2543 ms 265404 KB Output is correct
4 Correct 1253 ms 163852 KB Output is correct
5 Correct 2533 ms 265288 KB Output is correct
6 Correct 661 ms 108856 KB Output is correct
7 Correct 1478 ms 299856 KB Output is correct
8 Correct 1294 ms 38524 KB Output is correct
9 Correct 976 ms 37632 KB Output is correct
10 Correct 1304 ms 38632 KB Output is correct
11 Correct 518 ms 36752 KB Output is correct
12 Correct 1301 ms 38732 KB Output is correct
13 Correct 693 ms 37380 KB Output is correct
14 Correct 1080 ms 39112 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2506 ms 263040 KB Output is correct
2 Correct 152 ms 54820 KB Output is correct
3 Correct 2543 ms 265404 KB Output is correct
4 Correct 1253 ms 163852 KB Output is correct
5 Correct 2533 ms 265288 KB Output is correct
6 Correct 661 ms 108856 KB Output is correct
7 Correct 1478 ms 299856 KB Output is correct
8 Correct 1294 ms 38524 KB Output is correct
9 Correct 976 ms 37632 KB Output is correct
10 Correct 1304 ms 38632 KB Output is correct
11 Correct 518 ms 36752 KB Output is correct
12 Correct 1301 ms 38732 KB Output is correct
13 Correct 693 ms 37380 KB Output is correct
14 Correct 1080 ms 39112 KB Output is correct
15 Execution timed out 4064 ms 266548 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4062 ms 263500 KB Time limit exceeded
2 Halted 0 ms 0 KB -