oj.uz

답안 #526421

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
526421 2022-02-14T17:55:03 Z benson1029 Railway Trip 2 (JOI22_ho_t4) C++14
100 / 100
 1076 ms 347268 KB 
#include<bits/stdc++.h>
using namespace std;

int n,k,m;
int a[200005], b[200005];
int logb2[200005];
int l[200005][20], r[200005][20];
int liftl[200005][20], liftr[200005][20];
int sliftl[20][200005][20], sliftr[20][200005][20];
int q, s, t;

int qryl(int x, int y) {
	if(x<1) x = 1;
	if(y>n) y = n;
	int logv = logb2[y-x+1];
	return min(l[x][logv], l[y-(1<<logv)+1][logv]);
}

int qryr(int x, int y) {
	if(x<1) x = 1;
	if(y>n) y = n;
	int logv = logb2[y-x+1];
	return max(r[x][logv], r[y-(1<<logv)+1][logv]);
}

int sqryl(int id, int x, int y) {
	if(x<1) x = 1;
	if(y>n) y = n;
	int logv = logb2[y-x+1];
	return min(sliftl[id][x][logv], sliftl[id][y-(1<<logv)+1][logv]);
}

int sqryr(int id, int x, int y) {
	if(x<1) x = 1;
	if(y>n) y = n;
	int logv = logb2[y-x+1];
	return max(sliftr[id][x][logv], sliftr[id][y-(1<<logv)+1][logv]);
}

int main() {
	cin >> n >> k >> m;
	for(int i=0; (1<<i)<=n; i++) {
		logb2[(1<<i)] = i;
	}
	for(int i=2; i<=n; i++) {
		if(logb2[i]==0) logb2[i] = logb2[i-1];
	}
	for(int i=1; i<=n; i++) {
		l[i][0] = i;
		r[i][0] = i;
	}
	for(int i=0; i<m; i++) {
		cin >> a[i] >> b[i];
		if(a[i] > b[i]) {
			l[a[i]][0] = min(l[a[i]][0], b[i]);
		} else {
			r[a[i]][0] = max(r[a[i]][0], b[i]);
		}
	}
	for(int j=1; j<20; j++) {
		for(int i=1; i<=n; i++) {
			if(i+(1<<(j-1)) <= n) {
				l[i][j] = min(l[i][j-1], l[i+(1<<(j-1))][j-1]);
				r[i][j] = max(r[i][j-1], r[i+(1<<(j-1))][j-1]);
			}
		}
	}
	for(int j=0; j<20; j++) {
		if(j==0) {
			for(int i=1; i<=n; i++) {
				liftl[i][0] = qryl(i, i+k-1);
				liftr[i][0] = qryr(i-k+1, i);
			}
		} else {
			for(int i=1; i<=n; i++) {
				liftl[i][j] = sqryl(j-1, liftl[i][j-1], liftr[i][j-1]); //liftl[liftl[i][j-1]][j-1];
				liftr[i][j] = sqryr(j-1, liftl[i][j-1], liftr[i][j-1]);
			}
		}
		for(int i=1; i<=n; i++) {
			sliftl[j][i][0] = liftl[i][j];
			sliftr[j][i][0] = liftr[i][j];
		}
		for(int k=1; k<20; k++) {
			for(int i=1; i<=n; i++) {
				if(i+(1<<(k-1)) <= n) {
					sliftl[j][i][k] = min(sliftl[j][i][k-1], sliftl[j][i+(1<<(k-1))][k-1]);
					sliftr[j][i][k] = max(sliftr[j][i][k-1], sliftr[j][i+(1<<(k-1))][k-1]);
				}
			}
		}
	}
	cin >> q;
	while(q--) {
		cin >> s >> t;
		int ans = 0, orig = s;
		int l = s, r = s, ll, rr;
		for(int i=19; i>=0; i--) {
			ll = sqryl(i, l, r); rr = sqryr(i, l, r);
			if(!(ll <= t && t <= rr)) {
				l = ll;
				r = rr;
				ans += (1<<i);
			}
		}
		ll = sqryl(0, l, r); rr = sqryr(0, l, r);
		if(ll<=t && t<=rr) cout << ans+1 << "\n";
		else cout << "-1\n";
	}
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:96:16: warning: unused variable 'orig' [-Wunused-variable]
   96 |   int ans = 0, orig = s;
      |                ^~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1612 KB Output is correct
2 Correct 2 ms 1612 KB Output is correct
3 Correct 1 ms 1612 KB Output is correct
4 Correct 2 ms 1612 KB Output is correct
5 Correct 3 ms 1612 KB Output is correct
6 Correct 3 ms 1612 KB Output is correct
7 Correct 3 ms 1612 KB Output is correct
8 Correct 2 ms 1612 KB Output is correct
9 Correct 4 ms 1572 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 2 ms 1612 KB Output is correct
12 Correct 2 ms 1612 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1612 KB Output is correct
2 Correct 2 ms 1612 KB Output is correct
3 Correct 1 ms 1612 KB Output is correct
4 Correct 2 ms 1612 KB Output is correct
5 Correct 3 ms 1612 KB Output is correct
6 Correct 3 ms 1612 KB Output is correct
7 Correct 3 ms 1612 KB Output is correct
8 Correct 2 ms 1612 KB Output is correct
9 Correct 4 ms 1572 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 2 ms 1612 KB Output is correct
12 Correct 2 ms 1612 KB Output is correct
13 Correct 11 ms 7576 KB Output is correct
14 Correct 11 ms 7452 KB Output is correct
15 Correct 8 ms 7500 KB Output is correct
16 Correct 10 ms 7500 KB Output is correct
17 Correct 12 ms 7500 KB Output is correct
18 Correct 11 ms 7488 KB Output is correct
19 Correct 11 ms 7120 KB Output is correct
20 Correct 10 ms 7500 KB Output is correct
21 Correct 8 ms 7468 KB Output is correct
22 Correct 15 ms 7500 KB Output is correct
23 Correct 13 ms 7576 KB Output is correct
24 Correct 11 ms 7500 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 756 ms 346100 KB Output is correct
2 Correct 712 ms 345960 KB Output is correct
3 Correct 641 ms 346204 KB Output is correct
4 Correct 668 ms 345992 KB Output is correct
5 Correct 778 ms 347012 KB Output is correct
6 Correct 758 ms 346924 KB Output is correct
7 Correct 728 ms 347088 KB Output is correct
8 Correct 662 ms 342960 KB Output is correct
9 Correct 701 ms 346156 KB Output is correct
10 Correct 751 ms 346944 KB Output is correct
11 Correct 753 ms 347144 KB Output is correct

Subtask #4
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 915 ms 346252 KB Output is correct
2 Correct 909 ms 347264 KB Output is correct
3 Correct 930 ms 346488 KB Output is correct
4 Correct 865 ms 347108 KB Output is correct
5 Correct 951 ms 343592 KB Output is correct
6 Correct 952 ms 347112 KB Output is correct
7 Correct 1018 ms 347128 KB Output is correct
8 Correct 1029 ms 347216 KB Output is correct

Subtask #5
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1076 ms 347112 KB Output is correct
2 Correct 1028 ms 346504 KB Output is correct
3 Correct 995 ms 346088 KB Output is correct
4 Correct 1012 ms 345856 KB Output is correct
5 Correct 954 ms 345720 KB Output is correct
6 Correct 792 ms 345624 KB Output is correct
7 Correct 837 ms 346280 KB Output is correct
8 Correct 2 ms 1612 KB Output is correct
9 Correct 11 ms 7500 KB Output is correct
10 Correct 758 ms 346964 KB Output is correct
11 Correct 960 ms 347264 KB Output is correct
12 Correct 1006 ms 343608 KB Output is correct
13 Correct 949 ms 347024 KB Output is correct
14 Correct 3 ms 1612 KB Output is correct
15 Correct 12 ms 7480 KB Output is correct
16 Correct 798 ms 346960 KB Output is correct
17 Correct 915 ms 347184 KB Output is correct
18 Correct 927 ms 347248 KB Output is correct
19 Correct 935 ms 347236 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1612 KB Output is correct
2 Correct 2 ms 1612 KB Output is correct
3 Correct 1 ms 1612 KB Output is correct
4 Correct 2 ms 1612 KB Output is correct
5 Correct 3 ms 1612 KB Output is correct
6 Correct 3 ms 1612 KB Output is correct
7 Correct 3 ms 1612 KB Output is correct
8 Correct 2 ms 1612 KB Output is correct
9 Correct 4 ms 1572 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 2 ms 1612 KB Output is correct
12 Correct 2 ms 1612 KB Output is correct
13 Correct 11 ms 7576 KB Output is correct
14 Correct 11 ms 7452 KB Output is correct
15 Correct 8 ms 7500 KB Output is correct
16 Correct 10 ms 7500 KB Output is correct
17 Correct 12 ms 7500 KB Output is correct
18 Correct 11 ms 7488 KB Output is correct
19 Correct 11 ms 7120 KB Output is correct
20 Correct 10 ms 7500 KB Output is correct
21 Correct 8 ms 7468 KB Output is correct
22 Correct 15 ms 7500 KB Output is correct
23 Correct 13 ms 7576 KB Output is correct
24 Correct 11 ms 7500 KB Output is correct
25 Correct 756 ms 346100 KB Output is correct
26 Correct 712 ms 345960 KB Output is correct
27 Correct 641 ms 346204 KB Output is correct
28 Correct 668 ms 345992 KB Output is correct
29 Correct 778 ms 347012 KB Output is correct
30 Correct 758 ms 346924 KB Output is correct
31 Correct 728 ms 347088 KB Output is correct
32 Correct 662 ms 342960 KB Output is correct
33 Correct 701 ms 346156 KB Output is correct
34 Correct 751 ms 346944 KB Output is correct
35 Correct 753 ms 347144 KB Output is correct
36 Correct 915 ms 346252 KB Output is correct
37 Correct 909 ms 347264 KB Output is correct
38 Correct 930 ms 346488 KB Output is correct
39 Correct 865 ms 347108 KB Output is correct
40 Correct 951 ms 343592 KB Output is correct
41 Correct 952 ms 347112 KB Output is correct
42 Correct 1018 ms 347128 KB Output is correct
43 Correct 1029 ms 347216 KB Output is correct
44 Correct 1076 ms 347112 KB Output is correct
45 Correct 1028 ms 346504 KB Output is correct
46 Correct 995 ms 346088 KB Output is correct
47 Correct 1012 ms 345856 KB Output is correct
48 Correct 954 ms 345720 KB Output is correct
49 Correct 792 ms 345624 KB Output is correct
50 Correct 837 ms 346280 KB Output is correct
51 Correct 2 ms 1612 KB Output is correct
52 Correct 11 ms 7500 KB Output is correct
53 Correct 758 ms 346964 KB Output is correct
54 Correct 960 ms 347264 KB Output is correct
55 Correct 1006 ms 343608 KB Output is correct
56 Correct 949 ms 347024 KB Output is correct
57 Correct 3 ms 1612 KB Output is correct
58 Correct 12 ms 7480 KB Output is correct
59 Correct 798 ms 346960 KB Output is correct
60 Correct 915 ms 347184 KB Output is correct
61 Correct 927 ms 347248 KB Output is correct
62 Correct 935 ms 347236 KB Output is correct
63 Correct 955 ms 346184 KB Output is correct
64 Correct 918 ms 346476 KB Output is correct
65 Correct 876 ms 346324 KB Output is correct
66 Correct 858 ms 347188 KB Output is correct
67 Correct 931 ms 347268 KB Output is correct
68 Correct 841 ms 343632 KB Output is correct
69 Correct 802 ms 347032 KB Output is correct
70 Correct 902 ms 347224 KB Output is correct
71 Correct 945 ms 347184 KB Output is correct