oj.uz

Submission #879216

# Submission time Handle Problem Language Result Execution time Memory
879216 2023-11-26T23:11:52 Z samek08 Railway Trip 2 (JOI22_ho_t4) C++14
62 / 100
 552 ms 108560 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 == 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 35 ms 105308 KB Output is correct
2 Correct 25 ms 105140 KB Output is correct
3 Correct 24 ms 105284 KB Output is correct
4 Correct 24 ms 105304 KB Output is correct
5 Correct 24 ms 105232 KB Output is correct
6 Correct 24 ms 105092 KB Output is correct
7 Correct 24 ms 105304 KB Output is correct
8 Correct 24 ms 105308 KB Output is correct
9 Correct 24 ms 105308 KB Output is correct
10 Correct 24 ms 105320 KB Output is correct
11 Correct 25 ms 105308 KB Output is correct
12 Correct 24 ms 105040 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 105308 KB Output is correct
2 Correct 25 ms 105140 KB Output is correct
3 Correct 24 ms 105284 KB Output is correct
4 Correct 24 ms 105304 KB Output is correct
5 Correct 24 ms 105232 KB Output is correct
6 Correct 24 ms 105092 KB Output is correct
7 Correct 24 ms 105304 KB Output is correct
8 Correct 24 ms 105308 KB Output is correct
9 Correct 24 ms 105308 KB Output is correct
10 Correct 24 ms 105320 KB Output is correct
11 Correct 25 ms 105308 KB Output is correct
12 Correct 24 ms 105040 KB Output is correct
13 Correct 29 ms 105296 KB Output is correct
14 Correct 30 ms 105308 KB Output is correct
15 Correct 26 ms 105240 KB Output is correct
16 Correct 29 ms 105272 KB Output is correct
17 Correct 32 ms 105312 KB Output is correct
18 Correct 28 ms 105296 KB Output is correct
19 Correct 27 ms 105156 KB Output is correct
20 Correct 28 ms 105304 KB Output is correct
21 Correct 25 ms 105296 KB Output is correct
22 Correct 27 ms 105300 KB Output is correct
23 Correct 28 ms 105296 KB Output is correct
24 Correct 27 ms 105300 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 105808 KB Output is correct
2 Correct 224 ms 105808 KB Output is correct
3 Correct 269 ms 105796 KB Output is correct
4 Correct 209 ms 105708 KB Output is correct
5 Correct 175 ms 105688 KB Output is correct
6 Correct 203 ms 107856 KB Output is correct
7 Correct 162 ms 107456 KB Output is correct
8 Correct 155 ms 106824 KB Output is correct
9 Correct 143 ms 106804 KB Output is correct
10 Correct 168 ms 107852 KB Output is correct
11 Correct 185 ms 107860 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 105960 KB Output is correct
2 Incorrect 263 ms 108560 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 552 ms 106196 KB Output is correct
2 Correct 444 ms 106120 KB Output is correct
3 Correct 417 ms 106224 KB Output is correct
4 Correct 447 ms 105992 KB Output is correct
5 Correct 289 ms 106064 KB Output is correct
6 Correct 395 ms 105812 KB Output is correct
7 Correct 324 ms 105924 KB Output is correct
8 Correct 25 ms 105172 KB Output is correct
9 Correct 29 ms 105272 KB Output is correct
10 Correct 309 ms 107856 KB Output is correct
11 Correct 346 ms 108112 KB Output is correct
12 Correct 331 ms 108120 KB Output is correct
13 Correct 339 ms 108248 KB Output is correct
14 Correct 24 ms 105308 KB Output is correct
15 Correct 29 ms 105300 KB Output is correct
16 Correct 267 ms 107856 KB Output is correct
17 Correct 514 ms 108540 KB Output is correct
18 Correct 480 ms 108296 KB Output is correct
19 Correct 438 ms 108300 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 105308 KB Output is correct
2 Correct 25 ms 105140 KB Output is correct
3 Correct 24 ms 105284 KB Output is correct
4 Correct 24 ms 105304 KB Output is correct
5 Correct 24 ms 105232 KB Output is correct
6 Correct 24 ms 105092 KB Output is correct
7 Correct 24 ms 105304 KB Output is correct
8 Correct 24 ms 105308 KB Output is correct
9 Correct 24 ms 105308 KB Output is correct
10 Correct 24 ms 105320 KB Output is correct
11 Correct 25 ms 105308 KB Output is correct
12 Correct 24 ms 105040 KB Output is correct
13 Correct 29 ms 105296 KB Output is correct
14 Correct 30 ms 105308 KB Output is correct
15 Correct 26 ms 105240 KB Output is correct
16 Correct 29 ms 105272 KB Output is correct
17 Correct 32 ms 105312 KB Output is correct
18 Correct 28 ms 105296 KB Output is correct
19 Correct 27 ms 105156 KB Output is correct
20 Correct 28 ms 105304 KB Output is correct
21 Correct 25 ms 105296 KB Output is correct
22 Correct 27 ms 105300 KB Output is correct
23 Correct 28 ms 105296 KB Output is correct
24 Correct 27 ms 105300 KB Output is correct
25 Correct 233 ms 105808 KB Output is correct
26 Correct 224 ms 105808 KB Output is correct
27 Correct 269 ms 105796 KB Output is correct
28 Correct 209 ms 105708 KB Output is correct
29 Correct 175 ms 105688 KB Output is correct
30 Correct 203 ms 107856 KB Output is correct
31 Correct 162 ms 107456 KB Output is correct
32 Correct 155 ms 106824 KB Output is correct
33 Correct 143 ms 106804 KB Output is correct
34 Correct 168 ms 107852 KB Output is correct
35 Correct 185 ms 107860 KB Output is correct
36 Correct 303 ms 105960 KB Output is correct
37 Incorrect 263 ms 108560 KB Output isn't correct
38 Halted 0 ms 0 KB -