oj.uz

Submission #445641

# Submission time Handle Problem Language Result Execution time Memory
445641 2021-07-19T07:41:00 Z grt Specijacija (COCI20_specijacija) C++17
20 / 110
 4000 ms 803040 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[nax][19], dp[nax];
ll inv[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 2910 ms 802192 KB Output is correct
2 Correct 221 ms 127756 KB Output is correct
3 Correct 2967 ms 797372 KB Output is correct
4 Correct 1490 ms 427748 KB Output is correct
5 Correct 2946 ms 792452 KB Output is correct
6 Correct 845 ms 280856 KB Output is correct
7 Correct 2032 ms 788028 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2910 ms 802192 KB Output is correct
2 Correct 221 ms 127756 KB Output is correct
3 Correct 2967 ms 797372 KB Output is correct
4 Correct 1490 ms 427748 KB Output is correct
5 Correct 2946 ms 792452 KB Output is correct
6 Correct 845 ms 280856 KB Output is correct
7 Correct 2032 ms 788028 KB Output is correct
8 Correct 436 ms 71132 KB Output is correct
9 Correct 367 ms 69916 KB Output is correct
10 Correct 436 ms 71196 KB Output is correct
11 Correct 263 ms 68928 KB Output is correct
12 Correct 421 ms 71132 KB Output is correct
13 Correct 313 ms 69212 KB Output is correct
14 Correct 400 ms 71604 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2910 ms 802192 KB Output is correct
2 Correct 221 ms 127756 KB Output is correct
3 Correct 2967 ms 797372 KB Output is correct
4 Correct 1490 ms 427748 KB Output is correct
5 Correct 2946 ms 792452 KB Output is correct
6 Correct 845 ms 280856 KB Output is correct
7 Correct 2032 ms 788028 KB Output is correct
8 Correct 436 ms 71132 KB Output is correct
9 Correct 367 ms 69916 KB Output is correct
10 Correct 436 ms 71196 KB Output is correct
11 Correct 263 ms 68928 KB Output is correct
12 Correct 421 ms 71132 KB Output is correct
13 Correct 313 ms 69212 KB Output is correct
14 Correct 400 ms 71604 KB Output is correct
15 Execution timed out 4118 ms 803040 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 4151 ms 793332 KB Time limit exceeded
2 Halted 0 ms 0 KB -