Submission #879210

#	Time	Username	Problem	Language	Result	Execution time	Memory
879210		samek08	Railway Trip 2 (JOI22_ho_t4)	C++14	16 / 100	2063 ms	16996 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(a,b) for (int a = 0; a < (b); ++a)
#define pb push_back
#define all(t) t.begin(), t.end()

const int MAXN = 1e5+5, base = (1<<17), rozmiar_drzewa = base * 2, INF = 1e9+50, LG = 17;
int n = 0, k = 0, m = 0, q = 0, a = 0, b = 0;
vector<int> tree_min;
vector<int> tree_max;
int lewy[MAXN];
int prawy[MAXN];
int A_min[LG+1][MAXN];
int A_max[LG+1][MAXN];

inline void update_min(int l, int p, int val)
{
	l = l + base - 1, p = p + base + 1;
	while(l / 2 != p / 2)
	{
		if(l % 2 == 0) tree_min[l+1] = min(tree_min[l+1],val);
		if(p % 2 == 1) tree_min[p-1] = min(tree_min[p-1],val);
		l /= 2, p /= 2;
	}
}

inline void update_max(int l, int p, int val)
{
	l = l + base - 1, p = p + base + 1;
	while(l / 2 != p / 2)
	{
		if(l % 2 == 0) tree_max[l+1] = max(tree_max[l+1],val);
		if(p % 2 == 1) tree_max[p-1] = max(tree_max[p-1],val);
		l /= 2, p /= 2;
	}
}

inline int query_min(int v)
{
	int res = INF;
	v += base;
	while(v > 0)
	{
		res = min(res,tree_min[v]);
		v /= 2;
	}
	return res;
}

inline int query_max(int v)
{
	int res = -INF;
	v += base;
	while(v > 0)
	{
		res = max(res,tree_max[v]);
		v /= 2;
	}
	return res;
}

inline int query_min2(int l, int p)
{
	l = l + base - 1, p = p + base + 1;
	int res = INF;
	while(l / 2 != p / 2)
	{
		if(l % 2 == 0) res = min(res,tree_min[l+1]);
		if(p % 2 == 1) res = min(res,tree_min[p-1]);
		l /= 2, p /= 2;
	}
	return res;
}

inline int query_max2(int l, int p)
{
	l = l + base - 1, p = p + base + 1;
	int res = -INF;
	while(l / 2 != p / 2)
	{
		if(l % 2 == 0) res = max(res,tree_max[l+1]);
		if(p % 2 == 1) res = max(res,tree_max[p-1]);
		l /= 2, p /= 2;
	}
	return res;
}


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> k >> m;

	tree_min.assign(rozmiar_drzewa,INF);
	tree_max.assign(rozmiar_drzewa,-INF);
	rep(i,n)
	{
		tree_min[i+base] = i, tree_max[i+base] = i;
	}

	while(m--)
	{
		cin >> a >> b;
		--a,--b;
		if(a <= b) update_max(a,a+k-1,b);
		else update_min(a-k+1,a,b);
	}

	rep(i,n) A_min[0][i] = query_min(i);
	rep(i,n) A_max[0][i] = query_max(i);
	for(int i = 1; i <= LG; ++i)
	{
		rep(j,n)
		{
			A_min[i][j] = A_min[i-1][j], A_max[i][j] = A_max[i-1][j];
			for(int k = A_min[i-1][j]; k <= A_max[i-1][j]; ++k)
			{
				A_min[i][j] = min(A_min[i][j],A_min[i-1][k]);
				A_max[i][j] = max(A_max[i][j],A_max[i-1][k]);
			}
		}
	}

	//rep(i,n) cout << A_min[0][i] << " " << A_max[0][i] << '\n';

	tree_min.assign(rozmiar_drzewa,INF);
	tree_max.assign(rozmiar_drzewa,-INF);
	rep(i,n)
	{
		tree_min[i+base] = lewy[i], tree_max[i+base] = prawy[i];
	}
	for(int i = base - 1; i > 0; --i)
	{
		tree_min[i] = min(tree_min[i*2],tree_min[i*2+1]);
		tree_max[i] = max(tree_max[i*2],tree_max[i*2+1]);
	}

	cin >> q;
	while(q--)
	{
		cin >> a >> b;
		--a, --b;
		if(a == b)
		{
			cout << "0" << '\n';
			continue;
		}
		int l = a, p = a, wyn = 0;
		for(int i = LG; i >= 0; --i)
		{
			int l_zap = l, p_zap = p;
			for(int j = l; j <= p; ++j)
			{
				l_zap = min(l_zap,A_min[i][j]);
				p_zap = max(p_zap,A_max[i][j]);
			}
			//cout << "I: " << i << " WYN: " << wyn << " L: " << l << " P: " << p << " L ZAP: " << l_zap << " P ZAP: " << p_zap << " B: " << b << endl;
			if(b < l_zap or b > p_zap)
			{
				l = l_zap, p = p_zap;
				wyn += (1<<i);
			}
		}
		if(wyn == 262143) cout << "-1" << '\n';
		else cout << wyn+1 << '\n';
	}

	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 0 / 11
• Subtask 4: 0 / 25
• Subtask 5: 0 / 35
• Subtask 6: 0 / 13