oj.uz

Submission #879213

# Submission time Handle Problem Language Result Execution time Memory
879213 2023-11-26T23:00:05 Z samek08 Railway Trip 2 (JOI22_ho_t4) C++14
16 / 100
 538 ms 108620 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 = 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];
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);
		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,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(j,rozmiar_drzewa)
	{
		tree_minn[LG][j] = INF, tree_maxx[LG][j] = -INF;
	}
	rep(j,n)
	{
		tree_minn[LG][j+base] = A_min[LG][j], tree_maxx[LG][j+base] = A_max[LG][j];
	}
	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(wyn == 262143) cout << "-1" << '\n';
		else cout << wyn+1 << '\n';
	}

	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 53848 KB Output is correct
2 Correct 16 ms 53852 KB Output is correct
3 Correct 14 ms 53852 KB Output is correct
4 Correct 13 ms 53852 KB Output is correct
5 Correct 13 ms 53880 KB Output is correct
6 Correct 14 ms 53852 KB Output is correct
7 Correct 13 ms 53848 KB Output is correct
8 Correct 13 ms 53976 KB Output is correct
9 Correct 13 ms 53960 KB Output is correct
10 Correct 13 ms 53852 KB Output is correct
11 Correct 13 ms 53936 KB Output is correct
12 Correct 17 ms 53852 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 53848 KB Output is correct
2 Correct 16 ms 53852 KB Output is correct
3 Correct 14 ms 53852 KB Output is correct
4 Correct 13 ms 53852 KB Output is correct
5 Correct 13 ms 53880 KB Output is correct
6 Correct 14 ms 53852 KB Output is correct
7 Correct 13 ms 53848 KB Output is correct
8 Correct 13 ms 53976 KB Output is correct
9 Correct 13 ms 53960 KB Output is correct
10 Correct 13 ms 53852 KB Output is correct
11 Correct 13 ms 53936 KB Output is correct
12 Correct 17 ms 53852 KB Output is correct
13 Correct 18 ms 53848 KB Output is correct
14 Correct 18 ms 53852 KB Output is correct
15 Correct 15 ms 53852 KB Output is correct
16 Correct 18 ms 53852 KB Output is correct
17 Correct 17 ms 53852 KB Output is correct
18 Correct 16 ms 53848 KB Output is correct
19 Correct 16 ms 53852 KB Output is correct
20 Correct 16 ms 53852 KB Output is correct
21 Correct 16 ms 54012 KB Output is correct
22 Correct 15 ms 53852 KB Output is correct
23 Correct 16 ms 53852 KB Output is correct
24 Correct 16 ms 53848 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 53840 KB Output is correct
2 Correct 213 ms 53992 KB Output is correct
3 Correct 256 ms 53976 KB Output is correct
4 Correct 199 ms 53972 KB Output is correct
5 Runtime error 189 ms 106976 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 54616 KB Output is correct
2 Correct 458 ms 56280 KB Output is correct
3 Correct 389 ms 55220 KB Output is correct
4 Correct 421 ms 55132 KB Output is correct
5 Correct 241 ms 54708 KB Output is correct
6 Correct 351 ms 54608 KB Output is correct
7 Runtime error 355 ms 108620 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 53848 KB Output is correct
2 Correct 16 ms 53852 KB Output is correct
3 Correct 14 ms 53852 KB Output is correct
4 Correct 13 ms 53852 KB Output is correct
5 Correct 13 ms 53880 KB Output is correct
6 Correct 14 ms 53852 KB Output is correct
7 Correct 13 ms 53848 KB Output is correct
8 Correct 13 ms 53976 KB Output is correct
9 Correct 13 ms 53960 KB Output is correct
10 Correct 13 ms 53852 KB Output is correct
11 Correct 13 ms 53936 KB Output is correct
12 Correct 17 ms 53852 KB Output is correct
13 Correct 18 ms 53848 KB Output is correct
14 Correct 18 ms 53852 KB Output is correct
15 Correct 15 ms 53852 KB Output is correct
16 Correct 18 ms 53852 KB Output is correct
17 Correct 17 ms 53852 KB Output is correct
18 Correct 16 ms 53848 KB Output is correct
19 Correct 16 ms 53852 KB Output is correct
20 Correct 16 ms 53852 KB Output is correct
21 Correct 16 ms 54012 KB Output is correct
22 Correct 15 ms 53852 KB Output is correct
23 Correct 16 ms 53852 KB Output is correct
24 Correct 16 ms 53848 KB Output is correct
25 Correct 218 ms 53840 KB Output is correct
26 Correct 213 ms 53992 KB Output is correct
27 Correct 256 ms 53976 KB Output is correct
28 Correct 199 ms 53972 KB Output is correct
29 Runtime error 189 ms 106976 KB Execution killed with signal 6
30 Halted 0 ms 0 KB -