oj.uz

Submission #445642

# Submission time Handle Problem Language Result Execution time Memory
445642 2021-07-19T07:43:09 Z grt Specijacija (COCI20_specijacija) C++17
20 / 110
 4000 ms 778344 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<<19)];
vector<Node>T2[nax];
vector<Node>T3[(1<<19)];
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) {
		if(v >= R) {
			T1[v].PB({T1[v].back().g + x, ti, -1, -1});
		} else {
			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 2973 ms 777240 KB Output is correct
2 Correct 210 ms 103240 KB Output is correct
3 Correct 3013 ms 772972 KB Output is correct
4 Correct 1490 ms 403348 KB Output is correct
5 Correct 3021 ms 768280 KB Output is correct
6 Correct 861 ms 256576 KB Output is correct
7 Correct 2033 ms 763720 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2973 ms 777240 KB Output is correct
2 Correct 210 ms 103240 KB Output is correct
3 Correct 3013 ms 772972 KB Output is correct
4 Correct 1490 ms 403348 KB Output is correct
5 Correct 3021 ms 768280 KB Output is correct
6 Correct 861 ms 256576 KB Output is correct
7 Correct 2033 ms 763720 KB Output is correct
8 Correct 423 ms 46924 KB Output is correct
9 Correct 359 ms 45660 KB Output is correct
10 Correct 428 ms 47020 KB Output is correct
11 Correct 250 ms 44752 KB Output is correct
12 Correct 426 ms 46948 KB Output is correct
13 Correct 291 ms 44996 KB Output is correct
14 Correct 396 ms 47452 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2973 ms 777240 KB Output is correct
2 Correct 210 ms 103240 KB Output is correct
3 Correct 3013 ms 772972 KB Output is correct
4 Correct 1490 ms 403348 KB Output is correct
5 Correct 3021 ms 768280 KB Output is correct
6 Correct 861 ms 256576 KB Output is correct
7 Correct 2033 ms 763720 KB Output is correct
8 Correct 423 ms 46924 KB Output is correct
9 Correct 359 ms 45660 KB Output is correct
10 Correct 428 ms 47020 KB Output is correct
11 Correct 250 ms 44752 KB Output is correct
12 Correct 426 ms 46948 KB Output is correct
13 Correct 291 ms 44996 KB Output is correct
14 Correct 396 ms 47452 KB Output is correct
15 Execution timed out 4138 ms 778344 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 4150 ms 768836 KB Time limit exceeded
2 Halted 0 ms 0 KB -