oj.uz

Submission #879222

# Submission time Handle Problem Language Result Execution time Memory
879222 2023-11-26T23:17:33 Z samek08 Railway Trip 2 (JOI22_ho_t4) C++14
62 / 100
 561 ms 112212 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);
		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(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, ile = 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);
				++ile;
			}
		}
		if(ile == LG+1) cout << "-1" << '\n';
		else cout << wyn+1 << '\n';
	}

	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 111440 KB Output is correct
2 Correct 25 ms 111388 KB Output is correct
3 Correct 26 ms 111440 KB Output is correct
4 Correct 26 ms 111428 KB Output is correct
5 Correct 25 ms 111452 KB Output is correct
6 Correct 25 ms 111332 KB Output is correct
7 Correct 25 ms 111452 KB Output is correct
8 Correct 27 ms 111440 KB Output is correct
9 Correct 25 ms 111376 KB Output is correct
10 Correct 25 ms 111440 KB Output is correct
11 Correct 25 ms 111452 KB Output is correct
12 Correct 26 ms 111452 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 111440 KB Output is correct
2 Correct 25 ms 111388 KB Output is correct
3 Correct 26 ms 111440 KB Output is correct
4 Correct 26 ms 111428 KB Output is correct
5 Correct 25 ms 111452 KB Output is correct
6 Correct 25 ms 111332 KB Output is correct
7 Correct 25 ms 111452 KB Output is correct
8 Correct 27 ms 111440 KB Output is correct
9 Correct 25 ms 111376 KB Output is correct
10 Correct 25 ms 111440 KB Output is correct
11 Correct 25 ms 111452 KB Output is correct
12 Correct 26 ms 111452 KB Output is correct
13 Correct 31 ms 111452 KB Output is correct
14 Correct 31 ms 111452 KB Output is correct
15 Correct 28 ms 111440 KB Output is correct
16 Correct 33 ms 111444 KB Output is correct
17 Correct 29 ms 111436 KB Output is correct
18 Correct 30 ms 111452 KB Output is correct
19 Correct 28 ms 111448 KB Output is correct
20 Correct 29 ms 111452 KB Output is correct
21 Correct 27 ms 111452 KB Output is correct
22 Correct 31 ms 111440 KB Output is correct
23 Correct 29 ms 111452 KB Output is correct
24 Correct 29 ms 111448 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 111792 KB Output is correct
2 Correct 236 ms 111700 KB Output is correct
3 Correct 282 ms 111700 KB Output is correct
4 Correct 214 ms 111700 KB Output is correct
5 Correct 167 ms 111696 KB Output is correct
6 Correct 206 ms 111836 KB Output is correct
7 Correct 166 ms 111844 KB Output is correct
8 Correct 147 ms 111700 KB Output is correct
9 Correct 149 ms 111836 KB Output is correct
10 Correct 177 ms 111696 KB Output is correct
11 Correct 192 ms 111688 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 111960 KB Output is correct
2 Incorrect 294 ms 111840 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 112108 KB Output is correct
2 Correct 487 ms 112092 KB Output is correct
3 Correct 442 ms 112048 KB Output is correct
4 Correct 478 ms 112196 KB Output is correct
5 Correct 280 ms 111828 KB Output is correct
6 Correct 425 ms 112088 KB Output is correct
7 Correct 349 ms 111700 KB Output is correct
8 Correct 26 ms 111452 KB Output is correct
9 Correct 32 ms 111368 KB Output is correct
10 Correct 327 ms 111840 KB Output is correct
11 Correct 387 ms 111896 KB Output is correct
12 Correct 392 ms 111908 KB Output is correct
13 Correct 355 ms 111700 KB Output is correct
14 Correct 28 ms 111920 KB Output is correct
15 Correct 32 ms 111452 KB Output is correct
16 Correct 273 ms 111676 KB Output is correct
17 Correct 526 ms 112212 KB Output is correct
18 Correct 507 ms 112004 KB Output is correct
19 Correct 499 ms 111976 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 111440 KB Output is correct
2 Correct 25 ms 111388 KB Output is correct
3 Correct 26 ms 111440 KB Output is correct
4 Correct 26 ms 111428 KB Output is correct
5 Correct 25 ms 111452 KB Output is correct
6 Correct 25 ms 111332 KB Output is correct
7 Correct 25 ms 111452 KB Output is correct
8 Correct 27 ms 111440 KB Output is correct
9 Correct 25 ms 111376 KB Output is correct
10 Correct 25 ms 111440 KB Output is correct
11 Correct 25 ms 111452 KB Output is correct
12 Correct 26 ms 111452 KB Output is correct
13 Correct 31 ms 111452 KB Output is correct
14 Correct 31 ms 111452 KB Output is correct
15 Correct 28 ms 111440 KB Output is correct
16 Correct 33 ms 111444 KB Output is correct
17 Correct 29 ms 111436 KB Output is correct
18 Correct 30 ms 111452 KB Output is correct
19 Correct 28 ms 111448 KB Output is correct
20 Correct 29 ms 111452 KB Output is correct
21 Correct 27 ms 111452 KB Output is correct
22 Correct 31 ms 111440 KB Output is correct
23 Correct 29 ms 111452 KB Output is correct
24 Correct 29 ms 111448 KB Output is correct
25 Correct 253 ms 111792 KB Output is correct
26 Correct 236 ms 111700 KB Output is correct
27 Correct 282 ms 111700 KB Output is correct
28 Correct 214 ms 111700 KB Output is correct
29 Correct 167 ms 111696 KB Output is correct
30 Correct 206 ms 111836 KB Output is correct
31 Correct 166 ms 111844 KB Output is correct
32 Correct 147 ms 111700 KB Output is correct
33 Correct 149 ms 111836 KB Output is correct
34 Correct 177 ms 111696 KB Output is correct
35 Correct 192 ms 111688 KB Output is correct
36 Correct 310 ms 111960 KB Output is correct
37 Incorrect 294 ms 111840 KB Output isn't correct
38 Halted 0 ms 0 KB -