oj.uz

Submission #445640

# Submission time Handle Problem Language Result Execution time Memory
445640 2021-07-19T07:38:34 Z grt Specijacija (COCI20_specijacija) C++17
20 / 110
 4000 ms 803856 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[nax];
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});
}

inline void ustaw(int a, ll x, int ti) {
	T2[a].PB({x, ti, -1,-1});
}

inline ll askVal(int x) {
	return T2[x].back().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 ind = g(T2[x], ti);
	return T2[x][ind].g;
}

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});
		T3[i].PB({0, n + 2});
	}
	//cerr << "Done0\n";
	for(int i = 1; i <= n + 1; ++i) {
		add(i, i, i, n + 1, 0, R - 1, 1);
		ustaw(i, start + i - 1, n + 1);
		sc[start + i - 1];
	}
	//cerr << "Done\n";
	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);
		//cout << pos << " " << l << " " << r << "\n";
		ll val1 = askVal(l);
		ll val2 = askVal(pos);
		V[sc[seq[i]]].PB(sc[val1]);
		V[sc[seq[i]]].PB(sc[val2]);
		ustaw(l, 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 3051 ms 801852 KB Output is correct
2 Correct 257 ms 127900 KB Output is correct
3 Correct 3011 ms 797308 KB Output is correct
4 Correct 1513 ms 427684 KB Output is correct
5 Correct 2986 ms 792624 KB Output is correct
6 Correct 845 ms 281024 KB Output is correct
7 Correct 2033 ms 788072 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3051 ms 801852 KB Output is correct
2 Correct 257 ms 127900 KB Output is correct
3 Correct 3011 ms 797308 KB Output is correct
4 Correct 1513 ms 427684 KB Output is correct
5 Correct 2986 ms 792624 KB Output is correct
6 Correct 845 ms 281024 KB Output is correct
7 Correct 2033 ms 788072 KB Output is correct
8 Correct 425 ms 71140 KB Output is correct
9 Correct 376 ms 69956 KB Output is correct
10 Correct 430 ms 71156 KB Output is correct
11 Correct 262 ms 69060 KB Output is correct
12 Correct 442 ms 71092 KB Output is correct
13 Correct 326 ms 69184 KB Output is correct
14 Correct 400 ms 71592 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3051 ms 801852 KB Output is correct
2 Correct 257 ms 127900 KB Output is correct
3 Correct 3011 ms 797308 KB Output is correct
4 Correct 1513 ms 427684 KB Output is correct
5 Correct 2986 ms 792624 KB Output is correct
6 Correct 845 ms 281024 KB Output is correct
7 Correct 2033 ms 788072 KB Output is correct
8 Correct 425 ms 71140 KB Output is correct
9 Correct 376 ms 69956 KB Output is correct
10 Correct 430 ms 71156 KB Output is correct
11 Correct 262 ms 69060 KB Output is correct
12 Correct 442 ms 71092 KB Output is correct
13 Correct 326 ms 69184 KB Output is correct
14 Correct 400 ms 71592 KB Output is correct
15 Execution timed out 4114 ms 803856 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 4125 ms 793660 KB Time limit exceeded
2 Halted 0 ms 0 KB -