oj.uz

Submission #931693

# Submission time Handle Problem Language Result Execution time Memory
931693 2024-02-22T09:28:25 Z jcelin Railway Trip 2 (JOI22_ho_t4) C++14
100 / 100
 520 ms 348248 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<pll> vpll;

#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define all(x) (x).begin(), (x).end()

const int mod = 1e9 + 7; //998244353;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const int logo = 20;
const int MAXN = 2e5 + 7;
const int off = 1 << logo;
const int trsz = off << 1;
const int dx[] = {1, -1, 0, 0, -1, -1, 1, 1};
const int dy[] = {0, 0, -1, 1, 1, -1, 1, -1};


ii merge(ii a, ii b){
	return {min(a.X, b.X), max(a.Y, b.Y)};
}

struct t1{
	ii seg[trsz];
	
	
	t1(){
		fill(seg, seg + trsz, (ii){inf, -inf});
		for(int i=off+1; i<trsz; i++) seg[i] = {i - off, i - off};
	}
	
	void update(int l, int r, ii vl){
		for(l += off, r += off; l < r; l >>= 1, r >>= 1){
			if(l & 1) seg[l] = merge(seg[l], vl), l++;
			if(r & 1) --r, seg[r] = merge(seg[r], vl);
		}
	}
	
	ii query(int x){
		x += off;
		ii ret = seg[x];
		for(x /= 2; x; x /= 2) ret = merge(ret, seg[x]);
		return ret;
	}
}st;


struct sparse{
	ii seg[trsz];
	
	sparse(){
		for(int i=off; i<trsz; i++) seg[i] = {i - off, i - off};
	}
	
	void update(int x, ii vl){
		x += off;
		seg[x] = vl;
		for(x /= 2; x; x /= 2) seg[x] = merge(seg[x * 2], seg[x * 2 + 1]);
	}
	
	ii query(int l, int r){
		ii ret = {inf, -inf};
		for(l += off, r += off; l < r; l >>= 1, r >>= 1){
			if(l & 1) ret = merge(ret, seg[l++]);
			if(r & 1) ret = merge(ret, seg[--r]);
		}
		return ret;
	}
}t[logo];

void solve(){
	int n, m, k;
	cin >> n >> k >> m;
	while(m--){
		int l, r;
		cin >> l >> r;
		
		if(l < r){
			int li = l;
			int ri = min(l + k - 1, r);
			st.update(li, ri + 1, {inf, r});
		}else{
			swap(l, r);
			int li = max(r - k + 1, l);
			int ri  = r;
			st.update(li, ri + 1, {l, -inf});
		}
	}
	
	for(int i=1; i<=n; i++) t[0].update(i, st.query(i));
	
	for(int j=1; j<logo; j++) for(int i=1; i<=n; i++){
		ii pr = t[j - 1].query(i, i + 1);
		t[j].update(i, t[j - 1].query(pr.X, pr.Y + 1));
	}
	
	int q;
	cin >> q;
	while(q--){
		int u, v;
		cin >> u >> v;
		
		int ans = 0, l = u, r = u;
		for(int i=logo-1; i>=0; i--){
			ii nov = t[i].query(l, r + 1);
			if(!(nov.X <= v and nov.Y >= v)){
				ans += (1 << i);
				l = nov.X, r = nov.Y;
			}
		}
		
		if(ans > MAXN) cout << -1 << "\n";
		else cout << ans + 1 << "\n";
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int tt = 1;
	//cin >> tt;
	while(tt--) solve();
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 345172 KB Output is correct
2 Correct 105 ms 345052 KB Output is correct
3 Correct 105 ms 345052 KB Output is correct
4 Correct 105 ms 345420 KB Output is correct
5 Correct 109 ms 345120 KB Output is correct
6 Correct 109 ms 345172 KB Output is correct
7 Correct 105 ms 345168 KB Output is correct
8 Correct 106 ms 345140 KB Output is correct
9 Correct 109 ms 345168 KB Output is correct
10 Correct 106 ms 344916 KB Output is correct
11 Correct 108 ms 345188 KB Output is correct
12 Correct 106 ms 345176 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 345172 KB Output is correct
2 Correct 105 ms 345052 KB Output is correct
3 Correct 105 ms 345052 KB Output is correct
4 Correct 105 ms 345420 KB Output is correct
5 Correct 109 ms 345120 KB Output is correct
6 Correct 109 ms 345172 KB Output is correct
7 Correct 105 ms 345168 KB Output is correct
8 Correct 106 ms 345140 KB Output is correct
9 Correct 109 ms 345168 KB Output is correct
10 Correct 106 ms 344916 KB Output is correct
11 Correct 108 ms 345188 KB Output is correct
12 Correct 106 ms 345176 KB Output is correct
13 Correct 111 ms 345296 KB Output is correct
14 Correct 112 ms 345156 KB Output is correct
15 Correct 109 ms 345168 KB Output is correct
16 Correct 112 ms 345140 KB Output is correct
17 Correct 111 ms 345172 KB Output is correct
18 Correct 113 ms 345200 KB Output is correct
19 Correct 115 ms 345124 KB Output is correct
20 Correct 109 ms 344960 KB Output is correct
21 Correct 108 ms 345168 KB Output is correct
22 Correct 110 ms 345168 KB Output is correct
23 Correct 109 ms 345168 KB Output is correct
24 Correct 108 ms 345172 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 345940 KB Output is correct
2 Correct 338 ms 346160 KB Output is correct
3 Correct 360 ms 346204 KB Output is correct
4 Correct 327 ms 346192 KB Output is correct
5 Correct 341 ms 347276 KB Output is correct
6 Correct 320 ms 347728 KB Output is correct
7 Correct 355 ms 346964 KB Output is correct
8 Correct 343 ms 346320 KB Output is correct
9 Correct 332 ms 346324 KB Output is correct
10 Correct 325 ms 347236 KB Output is correct
11 Correct 333 ms 347352 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 346708 KB Output is correct
2 Correct 457 ms 348160 KB Output is correct
3 Correct 403 ms 347216 KB Output is correct
4 Correct 357 ms 347732 KB Output is correct
5 Correct 374 ms 347976 KB Output is correct
6 Correct 362 ms 347872 KB Output is correct
7 Correct 371 ms 348244 KB Output is correct
8 Correct 437 ms 348060 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 347980 KB Output is correct
2 Correct 448 ms 347076 KB Output is correct
3 Correct 450 ms 346452 KB Output is correct
4 Correct 454 ms 346056 KB Output is correct
5 Correct 348 ms 345940 KB Output is correct
6 Correct 411 ms 345936 KB Output is correct
7 Correct 382 ms 346820 KB Output is correct
8 Correct 109 ms 344928 KB Output is correct
9 Correct 112 ms 345112 KB Output is correct
10 Correct 392 ms 347480 KB Output is correct
11 Correct 420 ms 347920 KB Output is correct
12 Correct 425 ms 348092 KB Output is correct
13 Correct 406 ms 347984 KB Output is correct
14 Correct 103 ms 345036 KB Output is correct
15 Correct 109 ms 345172 KB Output is correct
16 Correct 356 ms 347472 KB Output is correct
17 Correct 484 ms 348244 KB Output is correct
18 Correct 457 ms 348096 KB Output is correct
19 Correct 451 ms 347972 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 345172 KB Output is correct
2 Correct 105 ms 345052 KB Output is correct
3 Correct 105 ms 345052 KB Output is correct
4 Correct 105 ms 345420 KB Output is correct
5 Correct 109 ms 345120 KB Output is correct
6 Correct 109 ms 345172 KB Output is correct
7 Correct 105 ms 345168 KB Output is correct
8 Correct 106 ms 345140 KB Output is correct
9 Correct 109 ms 345168 KB Output is correct
10 Correct 106 ms 344916 KB Output is correct
11 Correct 108 ms 345188 KB Output is correct
12 Correct 106 ms 345176 KB Output is correct
13 Correct 111 ms 345296 KB Output is correct
14 Correct 112 ms 345156 KB Output is correct
15 Correct 109 ms 345168 KB Output is correct
16 Correct 112 ms 345140 KB Output is correct
17 Correct 111 ms 345172 KB Output is correct
18 Correct 113 ms 345200 KB Output is correct
19 Correct 115 ms 345124 KB Output is correct
20 Correct 109 ms 344960 KB Output is correct
21 Correct 108 ms 345168 KB Output is correct
22 Correct 110 ms 345168 KB Output is correct
23 Correct 109 ms 345168 KB Output is correct
24 Correct 108 ms 345172 KB Output is correct
25 Correct 334 ms 345940 KB Output is correct
26 Correct 338 ms 346160 KB Output is correct
27 Correct 360 ms 346204 KB Output is correct
28 Correct 327 ms 346192 KB Output is correct
29 Correct 341 ms 347276 KB Output is correct
30 Correct 320 ms 347728 KB Output is correct
31 Correct 355 ms 346964 KB Output is correct
32 Correct 343 ms 346320 KB Output is correct
33 Correct 332 ms 346324 KB Output is correct
34 Correct 325 ms 347236 KB Output is correct
35 Correct 333 ms 347352 KB Output is correct
36 Correct 414 ms 346708 KB Output is correct
37 Correct 457 ms 348160 KB Output is correct
38 Correct 403 ms 347216 KB Output is correct
39 Correct 357 ms 347732 KB Output is correct
40 Correct 374 ms 347976 KB Output is correct
41 Correct 362 ms 347872 KB Output is correct
42 Correct 371 ms 348244 KB Output is correct
43 Correct 437 ms 348060 KB Output is correct
44 Correct 520 ms 347980 KB Output is correct
45 Correct 448 ms 347076 KB Output is correct
46 Correct 450 ms 346452 KB Output is correct
47 Correct 454 ms 346056 KB Output is correct
48 Correct 348 ms 345940 KB Output is correct
49 Correct 411 ms 345936 KB Output is correct
50 Correct 382 ms 346820 KB Output is correct
51 Correct 109 ms 344928 KB Output is correct
52 Correct 112 ms 345112 KB Output is correct
53 Correct 392 ms 347480 KB Output is correct
54 Correct 420 ms 347920 KB Output is correct
55 Correct 425 ms 348092 KB Output is correct
56 Correct 406 ms 347984 KB Output is correct
57 Correct 103 ms 345036 KB Output is correct
58 Correct 109 ms 345172 KB Output is correct
59 Correct 356 ms 347472 KB Output is correct
60 Correct 484 ms 348244 KB Output is correct
61 Correct 457 ms 348096 KB Output is correct
62 Correct 451 ms 347972 KB Output is correct
63 Correct 433 ms 346712 KB Output is correct
64 Correct 488 ms 346948 KB Output is correct
65 Correct 456 ms 346960 KB Output is correct
66 Correct 465 ms 347984 KB Output is correct
67 Correct 459 ms 348248 KB Output is correct
68 Correct 356 ms 347972 KB Output is correct
69 Correct 369 ms 347972 KB Output is correct
70 Correct 445 ms 348004 KB Output is correct
71 Correct 418 ms 348228 KB Output is correct