oj.uz

Submission #445551

# Submission time Handle Problem Language Result Execution time Memory
445551 2021-07-18T15:59:40 Z grt Specijacija (COCI20_specijacija) C++17
20 / 110
 4000 ms 267260 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];

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

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

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

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

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

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

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

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

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

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

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


__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 2484 ms 231860 KB Output is correct
2 Correct 148 ms 51912 KB Output is correct
3 Correct 2565 ms 231984 KB Output is correct
4 Correct 1246 ms 145592 KB Output is correct
5 Correct 2448 ms 231852 KB Output is correct
6 Correct 602 ms 98176 KB Output is correct
7 Correct 1417 ms 267260 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2484 ms 231860 KB Output is correct
2 Correct 148 ms 51912 KB Output is correct
3 Correct 2565 ms 231984 KB Output is correct
4 Correct 1246 ms 145592 KB Output is correct
5 Correct 2448 ms 231852 KB Output is correct
6 Correct 602 ms 98176 KB Output is correct
7 Correct 1417 ms 267260 KB Output is correct
8 Correct 1382 ms 35732 KB Output is correct
9 Correct 1038 ms 35260 KB Output is correct
10 Correct 1361 ms 35824 KB Output is correct
11 Correct 509 ms 34836 KB Output is correct
12 Correct 1433 ms 35704 KB Output is correct
13 Correct 717 ms 35300 KB Output is correct
14 Correct 1101 ms 36352 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2484 ms 231860 KB Output is correct
2 Correct 148 ms 51912 KB Output is correct
3 Correct 2565 ms 231984 KB Output is correct
4 Correct 1246 ms 145592 KB Output is correct
5 Correct 2448 ms 231852 KB Output is correct
6 Correct 602 ms 98176 KB Output is correct
7 Correct 1417 ms 267260 KB Output is correct
8 Correct 1382 ms 35732 KB Output is correct
9 Correct 1038 ms 35260 KB Output is correct
10 Correct 1361 ms 35824 KB Output is correct
11 Correct 509 ms 34836 KB Output is correct
12 Correct 1433 ms 35704 KB Output is correct
13 Correct 717 ms 35300 KB Output is correct
14 Correct 1101 ms 36352 KB Output is correct
15 Execution timed out 4111 ms 231664 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 4088 ms 232128 KB Time limit exceeded
2 Halted 0 ms 0 KB -