oj.uz

Submission #445631

# Submission time Handle Problem Language Result Execution time Memory
445631 2021-07-19T06:55:52 Z grt Specijacija (COCI20_specijacija) C++17
20 / 110
 4000 ms 473708 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)];
vector<pair<ll, int>>T3[(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;
	//}
//}

void add(int a, int b, int x, int ti, int l, int r, int v) {
	if(a <= l && r <= b) {
		T1[v].PB({T1[v].back().ST + x, ti});
		return;
	}
	int mid = (l + r) / 2;
	if(a <= mid) add(a, b, x, ti, l, mid, v*2);
	if(b > mid) add(a,b,x,ti,mid + 1,r,v*2+1);
	T3[v].PB({max(T3[2*v].back().ST + T1[2*v].back().ST, T3[2*v+1].back().ST + T1[2*v+1].back().ST), ti});
}

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

void debug() {
	for(int i = 1; i < 2 * R; ++i) {
		cout << "t1 " << i << ": ";
		for(auto x : T1[i]) cout << x.ST << " ";
		cout << "\n";
		cout << "t3 " << i << ": ";
		for(auto x : T3[i]) cout << x.ST << " ";
		cout << "\n";
	}
}

inline int f(int x) {
	int v = 1;
	int delta = 0;
	while(v < R) {
		delta += T1[v].back().ST;
		if(T3[2*v].back().ST + T1[2*v].back().ST + delta >= x) {
			v = v * 2;
		} else {
			v = v * 2 + 1;
		}
	}
	v -= R;
	if(v > n + 1) v = n + 2;
	return v;
}

inline int f2(int x, int ti) {
	int v = 1;
	int delta = 0;
	while(v < R) {
		delta += g(T1[v], ti).ST;
		if(g(T3[2*v],ti).ST + g(T1[2*v], ti).ST + delta >= x) {
			v = v * 2;
		} else {
			v = v * 2 + 1;
		}
	}
	v -= R;
	if(v > n + 1) v = n + 2;
	return v;
}

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 + 2) R *= 2;
	for(int i = 1; i < 2 * R; ++i) {
		T1[i].PB({0, n + 2});
		T2[i].PB({0, n + 2});
		T3[i].PB({0, n + 2});
	}
	for(int i = 1; i <= n + 1; ++i) {
		add(i, i, i, n + 1, 0, R - 1, 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;
		//cout << pos << " " << l << " " << r << "\n";
		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, 0, R - 1, 1);
		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 2684 ms 430980 KB Output is correct
2 Correct 183 ms 79868 KB Output is correct
3 Correct 2755 ms 431300 KB Output is correct
4 Correct 1355 ms 244716 KB Output is correct
5 Correct 2720 ms 431040 KB Output is correct
6 Correct 750 ms 160644 KB Output is correct
7 Correct 1778 ms 473708 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2684 ms 430980 KB Output is correct
2 Correct 183 ms 79868 KB Output is correct
3 Correct 2755 ms 431300 KB Output is correct
4 Correct 1355 ms 244716 KB Output is correct
5 Correct 2720 ms 431040 KB Output is correct
6 Correct 750 ms 160644 KB Output is correct
7 Correct 1778 ms 473708 KB Output is correct
8 Correct 677 ms 51088 KB Output is correct
9 Correct 550 ms 50116 KB Output is correct
10 Correct 673 ms 51240 KB Output is correct
11 Correct 333 ms 49140 KB Output is correct
12 Correct 679 ms 51288 KB Output is correct
13 Correct 422 ms 49664 KB Output is correct
14 Correct 575 ms 51960 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2684 ms 430980 KB Output is correct
2 Correct 183 ms 79868 KB Output is correct
3 Correct 2755 ms 431300 KB Output is correct
4 Correct 1355 ms 244716 KB Output is correct
5 Correct 2720 ms 431040 KB Output is correct
6 Correct 750 ms 160644 KB Output is correct
7 Correct 1778 ms 473708 KB Output is correct
8 Correct 677 ms 51088 KB Output is correct
9 Correct 550 ms 50116 KB Output is correct
10 Correct 673 ms 51240 KB Output is correct
11 Correct 333 ms 49140 KB Output is correct
12 Correct 679 ms 51288 KB Output is correct
13 Correct 422 ms 49664 KB Output is correct
14 Correct 575 ms 51960 KB Output is correct
15 Execution timed out 4099 ms 432876 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 4094 ms 432832 KB Time limit exceeded
2 Halted 0 ms 0 KB -