oj.uz

Submission #879219

# Submission time Handle Problem Language Result Execution time Memory
879219 2023-11-26T23:13:01 Z samek08 Railway Trip 2 (JOI22_ho_t4) C++14
62 / 100
 566 ms 106232 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 = 17;
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(wyn > n) cout << "-1" << '\n';
		else cout << wyn+1 << '\n';
	}

	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 105240 KB Output is correct
2 Correct 30 ms 105208 KB Output is correct
3 Correct 33 ms 105044 KB Output is correct
4 Correct 25 ms 105344 KB Output is correct
5 Correct 33 ms 105308 KB Output is correct
6 Correct 24 ms 105292 KB Output is correct
7 Correct 25 ms 105292 KB Output is correct
8 Correct 25 ms 105204 KB Output is correct
9 Correct 24 ms 105276 KB Output is correct
10 Correct 24 ms 105188 KB Output is correct
11 Correct 28 ms 105188 KB Output is correct
12 Correct 24 ms 105188 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 105240 KB Output is correct
2 Correct 30 ms 105208 KB Output is correct
3 Correct 33 ms 105044 KB Output is correct
4 Correct 25 ms 105344 KB Output is correct
5 Correct 33 ms 105308 KB Output is correct
6 Correct 24 ms 105292 KB Output is correct
7 Correct 25 ms 105292 KB Output is correct
8 Correct 25 ms 105204 KB Output is correct
9 Correct 24 ms 105276 KB Output is correct
10 Correct 24 ms 105188 KB Output is correct
11 Correct 28 ms 105188 KB Output is correct
12 Correct 24 ms 105188 KB Output is correct
13 Correct 32 ms 105272 KB Output is correct
14 Correct 30 ms 105236 KB Output is correct
15 Correct 26 ms 105308 KB Output is correct
16 Correct 33 ms 105220 KB Output is correct
17 Correct 33 ms 105304 KB Output is correct
18 Correct 31 ms 105508 KB Output is correct
19 Correct 27 ms 105308 KB Output is correct
20 Correct 31 ms 105196 KB Output is correct
21 Correct 27 ms 105292 KB Output is correct
22 Correct 30 ms 105132 KB Output is correct
23 Correct 29 ms 105248 KB Output is correct
24 Correct 29 ms 105308 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 105692 KB Output is correct
2 Correct 245 ms 105776 KB Output is correct
3 Correct 288 ms 105752 KB Output is correct
4 Correct 231 ms 106036 KB Output is correct
5 Correct 180 ms 105664 KB Output is correct
6 Correct 200 ms 105756 KB Output is correct
7 Correct 203 ms 105792 KB Output is correct
8 Correct 171 ms 105760 KB Output is correct
9 Correct 149 ms 105664 KB Output is correct
10 Correct 185 ms 105704 KB Output is correct
11 Correct 191 ms 105644 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 105976 KB Output is correct
2 Incorrect 297 ms 105964 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 566 ms 105908 KB Output is correct
2 Correct 556 ms 105956 KB Output is correct
3 Correct 496 ms 106212 KB Output is correct
4 Correct 525 ms 106020 KB Output is correct
5 Correct 264 ms 106176 KB Output is correct
6 Correct 424 ms 105924 KB Output is correct
7 Correct 331 ms 106108 KB Output is correct
8 Correct 25 ms 105276 KB Output is correct
9 Correct 30 ms 105284 KB Output is correct
10 Correct 320 ms 105796 KB Output is correct
11 Correct 342 ms 105724 KB Output is correct
12 Correct 347 ms 105704 KB Output is correct
13 Correct 359 ms 105888 KB Output is correct
14 Correct 27 ms 105192 KB Output is correct
15 Correct 33 ms 105252 KB Output is correct
16 Correct 287 ms 105956 KB Output is correct
17 Correct 544 ms 106152 KB Output is correct
18 Correct 491 ms 105936 KB Output is correct
19 Correct 498 ms 106232 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 105240 KB Output is correct
2 Correct 30 ms 105208 KB Output is correct
3 Correct 33 ms 105044 KB Output is correct
4 Correct 25 ms 105344 KB Output is correct
5 Correct 33 ms 105308 KB Output is correct
6 Correct 24 ms 105292 KB Output is correct
7 Correct 25 ms 105292 KB Output is correct
8 Correct 25 ms 105204 KB Output is correct
9 Correct 24 ms 105276 KB Output is correct
10 Correct 24 ms 105188 KB Output is correct
11 Correct 28 ms 105188 KB Output is correct
12 Correct 24 ms 105188 KB Output is correct
13 Correct 32 ms 105272 KB Output is correct
14 Correct 30 ms 105236 KB Output is correct
15 Correct 26 ms 105308 KB Output is correct
16 Correct 33 ms 105220 KB Output is correct
17 Correct 33 ms 105304 KB Output is correct
18 Correct 31 ms 105508 KB Output is correct
19 Correct 27 ms 105308 KB Output is correct
20 Correct 31 ms 105196 KB Output is correct
21 Correct 27 ms 105292 KB Output is correct
22 Correct 30 ms 105132 KB Output is correct
23 Correct 29 ms 105248 KB Output is correct
24 Correct 29 ms 105308 KB Output is correct
25 Correct 243 ms 105692 KB Output is correct
26 Correct 245 ms 105776 KB Output is correct
27 Correct 288 ms 105752 KB Output is correct
28 Correct 231 ms 106036 KB Output is correct
29 Correct 180 ms 105664 KB Output is correct
30 Correct 200 ms 105756 KB Output is correct
31 Correct 203 ms 105792 KB Output is correct
32 Correct 171 ms 105760 KB Output is correct
33 Correct 149 ms 105664 KB Output is correct
34 Correct 185 ms 105704 KB Output is correct
35 Correct 191 ms 105644 KB Output is correct
36 Correct 321 ms 105976 KB Output is correct
37 Incorrect 297 ms 105964 KB Output isn't correct
38 Halted 0 ms 0 KB -