oj.uz

Submission #445549

# Submission time Handle Problem Language Result Execution time Memory
445549 2021-07-18T15:54:17 Z grt Specijacija (COCI20_specijacija) C++17
20 / 110
 4000 ms 267424 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;
		ll val1 = askVal(l);
		ll 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 2391 ms 232140 KB Output is correct
2 Correct 131 ms 52000 KB Output is correct
3 Correct 2408 ms 231924 KB Output is correct
4 Correct 1199 ms 145484 KB Output is correct
5 Correct 2431 ms 231844 KB Output is correct
6 Correct 632 ms 98120 KB Output is correct
7 Correct 1387 ms 267424 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2391 ms 232140 KB Output is correct
2 Correct 131 ms 52000 KB Output is correct
3 Correct 2408 ms 231924 KB Output is correct
4 Correct 1199 ms 145484 KB Output is correct
5 Correct 2431 ms 231844 KB Output is correct
6 Correct 632 ms 98120 KB Output is correct
7 Correct 1387 ms 267424 KB Output is correct
8 Correct 1362 ms 35644 KB Output is correct
9 Correct 1014 ms 35400 KB Output is correct
10 Correct 1375 ms 35804 KB Output is correct
11 Correct 542 ms 35000 KB Output is correct
12 Correct 1366 ms 35800 KB Output is correct
13 Correct 736 ms 35120 KB Output is correct
14 Correct 1152 ms 36368 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2391 ms 232140 KB Output is correct
2 Correct 131 ms 52000 KB Output is correct
3 Correct 2408 ms 231924 KB Output is correct
4 Correct 1199 ms 145484 KB Output is correct
5 Correct 2431 ms 231844 KB Output is correct
6 Correct 632 ms 98120 KB Output is correct
7 Correct 1387 ms 267424 KB Output is correct
8 Correct 1362 ms 35644 KB Output is correct
9 Correct 1014 ms 35400 KB Output is correct
10 Correct 1375 ms 35804 KB Output is correct
11 Correct 542 ms 35000 KB Output is correct
12 Correct 1366 ms 35800 KB Output is correct
13 Correct 736 ms 35120 KB Output is correct
14 Correct 1152 ms 36368 KB Output is correct
15 Execution timed out 4086 ms 231896 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 4101 ms 232288 KB Time limit exceeded
2 Halted 0 ms 0 KB -