oj.uz

Submission #879223

# Submission time Handle Problem Language Result Execution time Memory
879223 2023-11-26T23:25:09 Z samek08 Railway Trip 2 (JOI22_ho_t4) C++14
62 / 100
 545 ms 112356 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;
		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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 111444 KB Output is correct
2 Correct 25 ms 111444 KB Output is correct
3 Correct 25 ms 111708 KB Output is correct
4 Correct 25 ms 111452 KB Output is correct
5 Correct 26 ms 111452 KB Output is correct
6 Correct 25 ms 111452 KB Output is correct
7 Correct 25 ms 111440 KB Output is correct
8 Correct 25 ms 111440 KB Output is correct
9 Correct 25 ms 111440 KB Output is correct
10 Correct 25 ms 111452 KB Output is correct
11 Correct 33 ms 111704 KB Output is correct
12 Correct 25 ms 111444 KB Output is correct

Subtask #2
8.0 / 8.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 111696 KB Output is correct
2 Correct 255 ms 111700 KB Output is correct
3 Correct 277 ms 111664 KB Output is correct
4 Correct 216 ms 111800 KB Output is correct
5 Correct 171 ms 111696 KB Output is correct
6 Correct 212 ms 111628 KB Output is correct
7 Correct 167 ms 111700 KB Output is correct
8 Correct 147 ms 111584 KB Output is correct
9 Correct 165 ms 111620 KB Output is correct
10 Correct 176 ms 111700 KB Output is correct
11 Correct 209 ms 111588 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 111932 KB Output is correct
2 Incorrect 214 ms 111824 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 332 ms 112080 KB Output is correct
2 Correct 523 ms 111952 KB Output is correct
3 Correct 464 ms 112356 KB Output is correct
4 Correct 503 ms 112064 KB Output is correct
5 Correct 306 ms 112012 KB Output is correct
6 Correct 423 ms 111928 KB Output is correct
7 Correct 344 ms 111700 KB Output is correct
8 Correct 26 ms 111448 KB Output is correct
9 Correct 36 ms 111444 KB Output is correct
10 Correct 343 ms 111800 KB Output is correct
11 Correct 409 ms 111828 KB Output is correct
12 Correct 388 ms 111924 KB Output is correct
13 Correct 359 ms 111948 KB Output is correct
14 Correct 30 ms 111448 KB Output is correct
15 Correct 37 ms 111452 KB Output is correct
16 Correct 273 ms 111592 KB Output is correct
17 Correct 545 ms 112156 KB Output is correct
18 Correct 515 ms 111952 KB Output is correct
19 Correct 507 ms 112200 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 111444 KB Output is correct
2 Correct 25 ms 111444 KB Output is correct
3 Correct 25 ms 111708 KB Output is correct
4 Correct 25 ms 111452 KB Output is correct
5 Correct 26 ms 111452 KB Output is correct
6 Correct 25 ms 111452 KB Output is correct
7 Correct 25 ms 111440 KB Output is correct
8 Correct 25 ms 111440 KB Output is correct
9 Correct 25 ms 111440 KB Output is correct
10 Correct 25 ms 111452 KB Output is correct
11 Correct 33 ms 111704 KB Output is correct
12 Correct 25 ms 111444 KB Output is correct
13 Correct 31 ms 111468 KB Output is correct
14 Correct 30 ms 111444 KB Output is correct
15 Correct 30 ms 111452 KB Output is correct
16 Correct 27 ms 111440 KB Output is correct
17 Correct 29 ms 111440 KB Output is correct
18 Correct 32 ms 111704 KB Output is correct
19 Correct 28 ms 111452 KB Output is correct
20 Correct 29 ms 111432 KB Output is correct
21 Correct 27 ms 111416 KB Output is correct
22 Correct 29 ms 111440 KB Output is correct
23 Correct 29 ms 111444 KB Output is correct
24 Correct 29 ms 111452 KB Output is correct
25 Correct 259 ms 111696 KB Output is correct
26 Correct 255 ms 111700 KB Output is correct
27 Correct 277 ms 111664 KB Output is correct
28 Correct 216 ms 111800 KB Output is correct
29 Correct 171 ms 111696 KB Output is correct
30 Correct 212 ms 111628 KB Output is correct
31 Correct 167 ms 111700 KB Output is correct
32 Correct 147 ms 111584 KB Output is correct
33 Correct 165 ms 111620 KB Output is correct
34 Correct 176 ms 111700 KB Output is correct
35 Correct 209 ms 111588 KB Output is correct
36 Correct 295 ms 111932 KB Output is correct
37 Incorrect 214 ms 111824 KB Output isn't correct
38 Halted 0 ms 0 KB -