oj.uz

Submission #879224

# Submission time Handle Problem Language Result Execution time Memory
879224 2023-11-26T23:34:06 Z samek08 Railway Trip 2 (JOI22_ho_t4) C++14
0 / 100
 516 ms 112228 KB 
#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 = 2e5+5, base = (1<<18), rozmiar_drzewa = base * 2, INF = 1e9+50, LG = 18;
int n = 0, k = 0, m = 0, q = 0, a = 0, b = 0;
vector<int> tree_min;
vector<int> tree_max;
int A_min[LG+1][MAXN];
int A_max[LG+1][MAXN];
int tree_minn[LG+1][rozmiar_drzewa];
int tree_maxx[LG+1][rozmiar_drzewa];

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, int idx)
{
	l = l + base - 1, p = p + base + 1;
	int res = INF;
	while(l / 2 != p / 2)
	{
		if(l % 2 == 0) res = min(res,tree_minn[idx][l+1]);
		if(p % 2 == 1) res = min(res,tree_minn[idx][p-1]);
		l /= 2, p /= 2;
	}
	return res;
}

inline int query_max2(int l, int p, int idx)
{
	l = l + base - 1, p = p + base + 1;
	int res = -INF;
	while(l / 2 != p / 2)
	{
		if(l % 2 == 0) res = max(res,tree_maxx[idx][l+1]);
		if(p % 2 == 1) res = max(res,tree_maxx[idx][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);
			update_min(a,a+k-1,b);
		}
		else
		{
			update_max(a-k+1,a,b);
			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,rozmiar_drzewa)
		{
			tree_minn[i-1][j] = INF, tree_maxx[i-1][j] = -INF;
		}
		rep(j,n)
		{
			tree_minn[i-1][j+base] = A_min[i-1][j], tree_maxx[i-1][j+base] = A_max[i-1][j];
		}
		for(int j = base-1; j > 0; --j)
		{
			tree_minn[i-1][j] = min(tree_minn[i-1][j*2],tree_minn[i-1][j*2+1]);
			tree_maxx[i-1][j] = max(tree_maxx[i-1][j*2],tree_maxx[i-1][j*2+1]);
		}
		rep(j,n)
		{
			A_min[i][j] = min(A_min[i-1][j],query_min2(A_min[i-1][j],A_max[i-1][j],i-1)), A_max[i][j] = max(A_max[i-1][j],query_max2(A_min[i-1][j],A_max[i-1][j],i-1));
		}
	}
	rep(i,rozmiar_drzewa)
	{
		tree_minn[LG][i] = INF, tree_maxx[LG][i] = -INF;
	}
	rep(i,n)
	{
		tree_minn[LG][i+base] = A_min[LG][i], tree_maxx[LG][i+base] = A_max[LG][i];
	}
	for(int i = base-1; i > 0; --i)
	{
		tree_minn[LG][i] = min(tree_minn[LG][i*2],tree_minn[LG][i*2+1]);
		tree_maxx[LG][i] = max(tree_maxx[LG][i*2],tree_maxx[LG][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 = min(l,query_min2(l,p,i)), p_zap = max(p,query_max2(l,p,i));
			if(b < l_zap or b > p_zap)
			{
				l = l_zap, p = p_zap;
				wyn += (1<<i);
				if(i == LG)
				{
					wyn = -2;
					break;
				}
			}
		}
		cout << wyn+1 << '\n';
	}

	return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 111444 KB Output is correct
2 Correct 25 ms 111336 KB Output is correct
3 Correct 25 ms 111476 KB Output is correct
4 Incorrect 25 ms 111428 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 111444 KB Output is correct
2 Correct 25 ms 111336 KB Output is correct
3 Correct 25 ms 111476 KB Output is correct
4 Incorrect 25 ms 111428 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 111808 KB Output is correct
2 Correct 239 ms 111808 KB Output is correct
3 Correct 302 ms 111672 KB Output is correct
4 Correct 222 ms 111696 KB Output is correct
5 Incorrect 199 ms 111632 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 273 ms 111844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 111832 KB Output is correct
2 Correct 505 ms 112088 KB Output is correct
3 Correct 458 ms 112060 KB Output is correct
4 Correct 516 ms 112228 KB Output is correct
5 Correct 290 ms 111952 KB Output is correct
6 Correct 425 ms 112032 KB Output is correct
7 Correct 392 ms 111700 KB Output is correct
8 Correct 25 ms 111448 KB Output is correct
9 Correct 31 ms 111464 KB Output is correct
10 Correct 200 ms 111824 KB Output is correct
11 Correct 256 ms 111908 KB Output is correct
12 Correct 242 ms 111908 KB Output is correct
13 Correct 266 ms 111828 KB Output is correct
14 Correct 25 ms 111444 KB Output is correct
15 Incorrect 31 ms 111440 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 111444 KB Output is correct
2 Correct 25 ms 111336 KB Output is correct
3 Correct 25 ms 111476 KB Output is correct
4 Incorrect 25 ms 111428 KB Output isn't correct
5 Halted 0 ms 0 KB -