oj.uz

Submission #445636

# Submission time Handle Problem Language Result Execution time Memory
445636 2021-07-19T07:30:13 Z grt Specijacija (COCI20_specijacija) C++17
20 / 110
 4000 ms 907344 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];

struct Node {
	ll g;
	int ti, lft, rght;
};

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

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().g + x, ti, (int)T1[2*v].size() - 1, (int)T1[2*v+1].size() - 1});
		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().g + T1[2*v].back().g, T3[2*v+1].back().g + T1[2*v+1].back().g), ti, (int)T3[2*v].size() - 1, (int)T3[2*v+1].size() - 1});
	T1[v].PB({T1[v].back().g, ti, (int)T1[2*v].size() - 1, (int)T1[2*v+1].size() - 1});
}

//void ustaw(int a, int b, ll x, int ti, int l, int r, int v) {
	//if(a <= l && r <= b) {
		
	//}
//}
inline void ustaw(int a, int b, ll x, int ti) {
	a += R; b += R;
	T2[a].PB({x, ti, -1, -1});
	if(a != b) T2[b].PB({x, ti, -1, -1});
	while((a>>1) != (b>>1)) {
		if((a&1)==0) T2[a ^1].PB({x, ti, (int)T2[2*(a^1)].size() - 1, (int)T2[2*(a^1)+1].size() - 1});
		if(b&1) T2[b ^1].PB({x, ti, (int)T2[2*(b^1)].size() - 1, (int)T2[2*(b^1)+1].size() - 1});
		a >>=1;
		b >>=1;
	}
}

inline ll askVal(int x) {
	x += R;
	Node w = T2[x].back();
	while(x > 1) {
		x>>=1;
		if(w.ti > T2[x].back().ti) {
			w = T2[x].back();
		}
	}
	return w.g;
}

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

inline ll askVal2(int x, int ti) {
	int v = 1;
	int ind = g(T2[v], ti);
	pair<ll,int>w = {T2[v][ind].g, T2[v][ind].ti};
	int l = 0, r = R - 1, mid;
	while(v < R) {
		mid = (l + r) / 2;
		if(x <= mid) {
			//ind = T2[v][ind].lft;
			v = v * 2;
			r = mid;	
		} else {
			//ind = T2[v][ind].rght;
			v = v * 2 + 1;
			l = mid + 1;
		}
		ind = g(T2[v], ti);
		if(w.ND > T2[v][ind].ti) {
			w = {T2[v][ind].g, T2[v][ind].ti};
		}
	}
	return w.ST;
}

inline int f(int x) {
	int v = 1;
	int delta = 0;
	while(v < R) {
		delta += T1[v].back().g;
		if(T3[2*v].back().g + T1[2*v].back().g + 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 ind = g(T1[v], ti);
	int ind2 = g(T3[v], ti);
	int delta = 0;
	while(v < R) {
		delta += T1[v][ind].g; 
		if(T3[2*v][T3[v][ind2].lft].g + T1[2*v][T1[v][ind].lft].g + delta >= x) {
			ind = T1[v][ind].lft;
			ind2 = T3[v][ind2].lft;
			v = v * 2;
		} else {
			ind = T1[v][ind].rght;
			ind2 = T3[v][ind2].rght;
			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);
		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 3553 ms 844292 KB Output is correct
2 Correct 268 ms 147984 KB Output is correct
3 Correct 3495 ms 843856 KB Output is correct
4 Correct 1775 ms 466560 KB Output is correct
5 Correct 3424 ms 843516 KB Output is correct
6 Correct 961 ms 309092 KB Output is correct
7 Correct 2410 ms 907344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3553 ms 844292 KB Output is correct
2 Correct 268 ms 147984 KB Output is correct
3 Correct 3495 ms 843856 KB Output is correct
4 Correct 1775 ms 466560 KB Output is correct
5 Correct 3424 ms 843516 KB Output is correct
6 Correct 961 ms 309092 KB Output is correct
7 Correct 2410 ms 907344 KB Output is correct
8 Correct 538 ms 86536 KB Output is correct
9 Correct 464 ms 85248 KB Output is correct
10 Correct 540 ms 86508 KB Output is correct
11 Correct 302 ms 84248 KB Output is correct
12 Correct 536 ms 86592 KB Output is correct
13 Correct 370 ms 84456 KB Output is correct
14 Correct 501 ms 87364 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3553 ms 844292 KB Output is correct
2 Correct 268 ms 147984 KB Output is correct
3 Correct 3495 ms 843856 KB Output is correct
4 Correct 1775 ms 466560 KB Output is correct
5 Correct 3424 ms 843516 KB Output is correct
6 Correct 961 ms 309092 KB Output is correct
7 Correct 2410 ms 907344 KB Output is correct
8 Correct 538 ms 86536 KB Output is correct
9 Correct 464 ms 85248 KB Output is correct
10 Correct 540 ms 86508 KB Output is correct
11 Correct 302 ms 84248 KB Output is correct
12 Correct 536 ms 86592 KB Output is correct
13 Correct 370 ms 84456 KB Output is correct
14 Correct 501 ms 87364 KB Output is correct
15 Execution timed out 4117 ms 843976 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 4115 ms 844128 KB Time limit exceeded
2 Halted 0 ms 0 KB -