oj.uz

Submission #445550

# Submission time Handle Problem Language Result Execution time Memory
445550 2021-07-18T15:58:35 Z grt Specijacija (COCI20_specijacija) C++17
20 / 110
 4000 ms 267164 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>>1) != (b>>1)) {
		if((a&1)==0) T1[a^1].PB({T1[a^1].back().ST + x, ti});
		if(b&1) T1[b^1].PB({T1[b^1].back().ST + x, ti});
		a >>=1;
		b >>=1;
	}
}

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>>1) != (b>>1)) {
		if((a&1)==0) T2[a ^1].PB({x, ti});
		if(b&1) T2[b ^1].PB({x, ti});
		a >>=1;
		b >>=1;
	}
}

ll askVal(int x) {
	x += R;
	pair<ll,int> w = T2[x].back();
	while(x > 1) {
		x>>=1;
		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 >>= 1;
		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) >> 1;
		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 >>= 1;
		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 >>= 1;
		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) >> 1;
		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) >> 1;
		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) >> 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);
	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 2462 ms 231728 KB Output is correct
2 Correct 128 ms 52004 KB Output is correct
3 Correct 2407 ms 231920 KB Output is correct
4 Correct 1245 ms 145432 KB Output is correct
5 Correct 2445 ms 231912 KB Output is correct
6 Correct 614 ms 98092 KB Output is correct
7 Correct 1452 ms 267164 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2462 ms 231728 KB Output is correct
2 Correct 128 ms 52004 KB Output is correct
3 Correct 2407 ms 231920 KB Output is correct
4 Correct 1245 ms 145432 KB Output is correct
5 Correct 2445 ms 231912 KB Output is correct
6 Correct 614 ms 98092 KB Output is correct
7 Correct 1452 ms 267164 KB Output is correct
8 Correct 1354 ms 35700 KB Output is correct
9 Correct 1034 ms 35260 KB Output is correct
10 Correct 1383 ms 35768 KB Output is correct
11 Correct 559 ms 34988 KB Output is correct
12 Correct 1424 ms 35788 KB Output is correct
13 Correct 752 ms 35136 KB Output is correct
14 Correct 1150 ms 36304 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2462 ms 231728 KB Output is correct
2 Correct 128 ms 52004 KB Output is correct
3 Correct 2407 ms 231920 KB Output is correct
4 Correct 1245 ms 145432 KB Output is correct
5 Correct 2445 ms 231912 KB Output is correct
6 Correct 614 ms 98092 KB Output is correct
7 Correct 1452 ms 267164 KB Output is correct
8 Correct 1354 ms 35700 KB Output is correct
9 Correct 1034 ms 35260 KB Output is correct
10 Correct 1383 ms 35768 KB Output is correct
11 Correct 559 ms 34988 KB Output is correct
12 Correct 1424 ms 35788 KB Output is correct
13 Correct 752 ms 35136 KB Output is correct
14 Correct 1150 ms 36304 KB Output is correct
15 Execution timed out 4085 ms 231724 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 4075 ms 232048 KB Time limit exceeded
2 Halted 0 ms 0 KB -