oj.uz

Submission #624706

# Submission time Handle Problem Language Result Execution time Memory
624706 2022-08-08T15:51:14 Z QwertyPi Railway Trip 2 (JOI22_ho_t4) C++14
100 / 100
 540 ms 257744 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 100013;
int l[N], r[N];
int n, k;
 
struct SegTree{
	int tmin[N * 4] = {0}, tmax[N * 4] = {0};
	void build(int i = 0, int il = 0, int ir = n){
		if(ir - il == 1){
			tmin[i] = tmax[i] = il;
			return;
		}
		int mid = (il + ir) / 2;
		build(i * 2 + 1, il, mid);
		build(i * 2 + 2, mid, ir);
		tmin[i] = INT32_MAX;
		tmax[i] = INT32_MIN;
	}
	void upd_min(int l, int r, int v, int i = 0, int il = 0, int ir = n){
		if(r <= il || ir <= l)
			return;
		if(l <= il && ir <= r){
			tmin[i] = min(tmin[i], v);
			return;
		}
		tmin[i * 2 + 1] = min(tmin[i * 2 + 1], tmin[i]);
		tmin[i * 2 + 2] = min(tmin[i * 2 + 2], tmin[i]);
		int mid = (il + ir) / 2;
		upd_min(l, r, v, i * 2 + 1, il, mid);
		upd_min(l, r, v, i * 2 + 2, mid, ir);
	}
	void upd_max(int l, int r, int v, int i = 0, int il = 0, int ir = n){
		if(r <= il || ir <= l)
			return;
		if(l <= il && ir <= r){
			tmax[i] = max(tmax[i], v);
			return;
		}
		tmax[i * 2 + 1] = max(tmax[i * 2 + 1], tmax[i]);
		tmax[i * 2 + 2] = max(tmax[i * 2 + 2], tmax[i]);
		int mid = (il + ir) / 2;
		upd_max(l, r, v, i * 2 + 1, il, mid);
		upd_max(l, r, v, i * 2 + 2, mid, ir);
	}
	int qry_min(int idx, int i = 0, int il = 0, int ir = n){
		if(il + 1 == ir){
			return tmin[i];
		}
		tmin[i * 2 + 1] = min(tmin[i * 2 + 1], tmin[i]);
		tmin[i * 2 + 2] = min(tmin[i * 2 + 2], tmin[i]);
		int mid = (il + ir) / 2;
		if(idx >= mid){
			return qry_min(idx, i * 2 + 2, mid, ir);
		}else{
			return qry_min(idx, i * 2 + 1, il, mid);
		}
	}
	int qry_max(int idx, int i = 0, int il = 0, int ir = n){
		if(il + 1 == ir){
			return tmax[i];
		}
		tmax[i * 2 + 1] = max(tmax[i * 2 + 1], tmax[i]);
		tmax[i * 2 + 2] = max(tmax[i * 2 + 2], tmax[i]);
		int mid = (il + ir) / 2;
		if(idx >= mid){
			return qry_max(idx, i * 2 + 2, mid, ir);
		}else{
			return qry_max(idx, i * 2 + 1, il, mid);
		}
	}
};
 
struct SparseTable{
	int stl[20][N] = {0}, str[20][N] = {0};
	void build(int l[N], int r[N]){
		for(int i = 0; i < n; i++){
			stl[0][i] = l[i];
			str[0][i] = r[i];
		}
		for(int j = 1; j < 20; j++){
			for(int i = 0; i <= n - (1 << j); i++){
				stl[j][i] = min(stl[j - 1][i], stl[j - 1][i + (1 << j - 1)]);
				str[j][i] = max(str[j - 1][i], str[j - 1][i + (1 << j - 1)]);
			}
		}
	}
	int qry_l(int l, int r){
		int d = __lg(r - l + 1);
		return min(stl[d][l], stl[d][r - (1 << d) + 1]);
	}
	
	int qry_r(int l, int r){
		int d = __lg(r - l + 1);
		return max(str[d][l], str[d][r - (1 << d) + 1]);
	}
} st[20];
 
struct SparseTable2{
	int stl[20][N] = {0}, str[20][N] = {0};
	void build(int l[N], int r[N]){
		for(int i = 0; i < n; i++){
			stl[0][i] = l[i];
			str[0][i] = r[i];
		}
		for(int j = 1; j < 20; j++){
			st[j - 1].build(stl[j - 1], str[j - 1]);
			for(int i = 0; i < n; i++){
				stl[j][i] = st[j - 1].qry_l(stl[j - 1][i], str[j - 1][i]);
				str[j][i] = st[j - 1].qry_r(stl[j - 1][i], str[j - 1][i]);
			}
		}
	}
	int qry_l(int from, int to){
		if(stl[18][from] > to) return -1;
		int ret = 0;
		int l = from, r = from;
		for(int j = 18; j >= 0; j--){
			if(st[j].qry_l(l, r) > to){
				ret += (1 << j);
				int nl = st[j].qry_l(l, r);
				int nr = st[j].qry_r(l, r);
				l = nl, r = nr;
			}
		}
		return ret + 1;
	}
	int qry_r(int from, int to){
		if(str[18][from] < to) return -1;
		int ret = 0;
		int l = from, r = from;
		for(int j = 18; j >= 0; j--){
			if(st[j].qry_r(l, r) < to){
				ret += (1 << j);
				int nl = st[j].qry_l(l, r);
				int nr = st[j].qry_r(l, r);
				l = nl, r = nr;
			}
		}
		return ret + 1;
	}
} st2;
 
int main(){
	cin >> n >> k;
	int m;
	cin >> m;
	SegTree segtree;
	segtree.build();
	for(int i = 0; i < n; i++){
		l[i] = segtree.qry_min(i);
		r[i] = segtree.qry_max(i);
	}
	for(int i = 0; i < m; i++){
		int a, b;
		cin >> a >> b;
		a--; b--;
		if(a < b){
			segtree.upd_max(a, min(b - 1, a + k - 1) + 1, b);
		}else{
			segtree.upd_min(max(b + 1, a - k + 1), a + 1, b);
		}
	}
	
	for(int i = 0; i < n; i++){
		l[i] = segtree.qry_min(i);
		r[i] = segtree.qry_max(i);
	}
	
	st2.build(l, r);
	
	int q;
	cin >> q;
	for(int i = 0; i < q; i++){
		int s, t;
		cin >> s >> t;
		s--; t--;
		if(s < t){
			cout << st2.qry_r(s, t) << endl;
		}else{
			cout << st2.qry_l(s, t) << endl;
		}
	}
}

Compilation message

Main.cpp: In member function 'void SparseTable::build(int*, int*)':
Main.cpp:85:59: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   85 |     stl[j][i] = min(stl[j - 1][i], stl[j - 1][i + (1 << j - 1)]);
      |                                                         ~~^~~
Main.cpp:86:59: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   86 |     str[j][i] = max(str[j - 1][i], str[j - 1][i + (1 << j - 1)]);
      |                                                         ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Correct 3 ms 5716 KB Output is correct
5 Correct 3 ms 5716 KB Output is correct
6 Correct 3 ms 5716 KB Output is correct
7 Correct 4 ms 5716 KB Output is correct
8 Correct 3 ms 5716 KB Output is correct
9 Correct 3 ms 5716 KB Output is correct
10 Correct 2 ms 4052 KB Output is correct
11 Correct 3 ms 5716 KB Output is correct
12 Correct 3 ms 5716 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Correct 3 ms 5716 KB Output is correct
5 Correct 3 ms 5716 KB Output is correct
6 Correct 3 ms 5716 KB Output is correct
7 Correct 4 ms 5716 KB Output is correct
8 Correct 3 ms 5716 KB Output is correct
9 Correct 3 ms 5716 KB Output is correct
10 Correct 2 ms 4052 KB Output is correct
11 Correct 3 ms 5716 KB Output is correct
12 Correct 3 ms 5716 KB Output is correct
13 Correct 9 ms 9032 KB Output is correct
14 Correct 9 ms 8916 KB Output is correct
15 Correct 6 ms 8916 KB Output is correct
16 Correct 10 ms 8916 KB Output is correct
17 Correct 12 ms 8916 KB Output is correct
18 Correct 13 ms 8960 KB Output is correct
19 Correct 14 ms 8788 KB Output is correct
20 Correct 10 ms 8916 KB Output is correct
21 Correct 6 ms 8988 KB Output is correct
22 Correct 10 ms 8976 KB Output is correct
23 Correct 10 ms 8960 KB Output is correct
24 Correct 10 ms 9024 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 255340 KB Output is correct
2 Correct 249 ms 255348 KB Output is correct
3 Correct 227 ms 255556 KB Output is correct
4 Correct 222 ms 255316 KB Output is correct
5 Correct 343 ms 256816 KB Output is correct
6 Correct 311 ms 256852 KB Output is correct
7 Correct 313 ms 256512 KB Output is correct
8 Correct 269 ms 254412 KB Output is correct
9 Correct 269 ms 255808 KB Output is correct
10 Correct 315 ms 256844 KB Output is correct
11 Correct 335 ms 256852 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 256116 KB Output is correct
2 Correct 432 ms 257524 KB Output is correct
3 Correct 394 ms 256384 KB Output is correct
4 Correct 407 ms 257104 KB Output is correct
5 Correct 524 ms 256212 KB Output is correct
6 Correct 432 ms 257420 KB Output is correct
7 Correct 467 ms 257436 KB Output is correct
8 Correct 469 ms 257476 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 256512 KB Output is correct
2 Correct 408 ms 256476 KB Output is correct
3 Correct 377 ms 255832 KB Output is correct
4 Correct 330 ms 255536 KB Output is correct
5 Correct 284 ms 255284 KB Output is correct
6 Correct 293 ms 255176 KB Output is correct
7 Correct 342 ms 256284 KB Output is correct
8 Correct 3 ms 5716 KB Output is correct
9 Correct 9 ms 8956 KB Output is correct
10 Correct 374 ms 256848 KB Output is correct
11 Correct 431 ms 257356 KB Output is correct
12 Correct 433 ms 256216 KB Output is correct
13 Correct 419 ms 257376 KB Output is correct
14 Correct 4 ms 5660 KB Output is correct
15 Correct 10 ms 9044 KB Output is correct
16 Correct 304 ms 256852 KB Output is correct
17 Correct 479 ms 257624 KB Output is correct
18 Correct 429 ms 257496 KB Output is correct
19 Correct 430 ms 257504 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Correct 3 ms 5716 KB Output is correct
5 Correct 3 ms 5716 KB Output is correct
6 Correct 3 ms 5716 KB Output is correct
7 Correct 4 ms 5716 KB Output is correct
8 Correct 3 ms 5716 KB Output is correct
9 Correct 3 ms 5716 KB Output is correct
10 Correct 2 ms 4052 KB Output is correct
11 Correct 3 ms 5716 KB Output is correct
12 Correct 3 ms 5716 KB Output is correct
13 Correct 9 ms 9032 KB Output is correct
14 Correct 9 ms 8916 KB Output is correct
15 Correct 6 ms 8916 KB Output is correct
16 Correct 10 ms 8916 KB Output is correct
17 Correct 12 ms 8916 KB Output is correct
18 Correct 13 ms 8960 KB Output is correct
19 Correct 14 ms 8788 KB Output is correct
20 Correct 10 ms 8916 KB Output is correct
21 Correct 6 ms 8988 KB Output is correct
22 Correct 10 ms 8976 KB Output is correct
23 Correct 10 ms 8960 KB Output is correct
24 Correct 10 ms 9024 KB Output is correct
25 Correct 231 ms 255340 KB Output is correct
26 Correct 249 ms 255348 KB Output is correct
27 Correct 227 ms 255556 KB Output is correct
28 Correct 222 ms 255316 KB Output is correct
29 Correct 343 ms 256816 KB Output is correct
30 Correct 311 ms 256852 KB Output is correct
31 Correct 313 ms 256512 KB Output is correct
32 Correct 269 ms 254412 KB Output is correct
33 Correct 269 ms 255808 KB Output is correct
34 Correct 315 ms 256844 KB Output is correct
35 Correct 335 ms 256852 KB Output is correct
36 Correct 349 ms 256116 KB Output is correct
37 Correct 432 ms 257524 KB Output is correct
38 Correct 394 ms 256384 KB Output is correct
39 Correct 407 ms 257104 KB Output is correct
40 Correct 524 ms 256212 KB Output is correct
41 Correct 432 ms 257420 KB Output is correct
42 Correct 467 ms 257436 KB Output is correct
43 Correct 469 ms 257476 KB Output is correct
44 Correct 431 ms 256512 KB Output is correct
45 Correct 408 ms 256476 KB Output is correct
46 Correct 377 ms 255832 KB Output is correct
47 Correct 330 ms 255536 KB Output is correct
48 Correct 284 ms 255284 KB Output is correct
49 Correct 293 ms 255176 KB Output is correct
50 Correct 342 ms 256284 KB Output is correct
51 Correct 3 ms 5716 KB Output is correct
52 Correct 9 ms 8956 KB Output is correct
53 Correct 374 ms 256848 KB Output is correct
54 Correct 431 ms 257356 KB Output is correct
55 Correct 433 ms 256216 KB Output is correct
56 Correct 419 ms 257376 KB Output is correct
57 Correct 4 ms 5660 KB Output is correct
58 Correct 10 ms 9044 KB Output is correct
59 Correct 304 ms 256852 KB Output is correct
60 Correct 479 ms 257624 KB Output is correct
61 Correct 429 ms 257496 KB Output is correct
62 Correct 430 ms 257504 KB Output is correct
63 Correct 383 ms 256184 KB Output is correct
64 Correct 393 ms 256420 KB Output is correct
65 Correct 391 ms 256212 KB Output is correct
66 Correct 431 ms 257548 KB Output is correct
67 Correct 481 ms 257744 KB Output is correct
68 Correct 436 ms 256272 KB Output is correct
69 Correct 437 ms 257492 KB Output is correct
70 Correct 409 ms 257540 KB Output is correct
71 Correct 540 ms 257704 KB Output is correct