제출 #445635

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
445635		grt	Specijacija (COCI20_specijacija)	C++17	20 / 110	4130 ms	662040 KiB

Main

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

//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; //g(T1[v], ti).ST;
		if(T3[2*v][g(T3[2*v], ti)].g + T1[2*v][g(T1[2*v], ti)].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;
		}
		ind = g(T1[v], ti);
		ind2 = g(T3[v], ti);
	}
	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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60