oj.uz

Submission #116622

# Submission time Handle Problem Language Result Execution time Memory
116622 2019-06-13T08:30:36 Z tmwilliamlin168 Railway Trip (JOI17_railway_trip) C++14
100 / 100
 267 ms 14968 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN=1e5;
int n, k, q, l[mxN], nl[17][mxN], nr[17][mxN];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k >> q;
	for(int i=0; i<n; ++i) {
		cin >> l[i];
		nl[0][i]=i-1;
		while(~nl[0][i]&&l[nl[0][i]]<l[i])
			nl[0][i]=nl[0][nl[0][i]];
	}
	nl[0][0]=0;
	for(int i=n-1; ~i; --i) {
		nr[0][i]=i+1;
		while(nr[0][i]<n&&l[nr[0][i]]<l[i])
			nr[0][i]=nr[0][nr[0][i]];
	}
	nr[0][n-1]=n-1;
	for(int i=1; i<17; ++i) {
		for(int j=0; j<n; ++j) {
			nl[i][j]=min(nl[i-1][nl[i-1][j]], nl[i-1][nr[i-1][j]]);
			nr[i][j]=max(nr[i-1][nl[i-1][j]], nr[i-1][nr[i-1][j]]);
		}
	}
	for(int a, b; q--; ) {
		cin >> a >> b, --a, --b;
		if(a>b)
			swap(a, b);
		int l=a, r=a, ans=0, c;
		for(int i=16; ~i; --i) {
			if(max(nr[i][l], nr[i][r])<b) {
				tie(l, r)=make_pair(min(nl[i][l], nl[i][r]), max(nr[i][l], nr[i][r]));
				ans+=1<<i;
			}
		}
		c=r;
		l=b, r=b;
		for(int i=16; ~i; --i) {
			if(min(nl[i][l], nl[i][r])>c) {
				tie(l, r)=make_pair(min(nl[i][l], nl[i][r]), max(nr[i][l], nr[i][r]));
				ans+=1<<i;
			}
		}
		cout << ans << "\n";
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 22 ms 14212 KB Output is correct
3 Correct 23 ms 14208 KB Output is correct
4 Correct 23 ms 14336 KB Output is correct
5 Correct 23 ms 14328 KB Output is correct
6 Correct 23 ms 14336 KB Output is correct
7 Correct 26 ms 14464 KB Output is correct
8 Correct 20 ms 14204 KB Output is correct
9 Correct 23 ms 14220 KB Output is correct
10 Correct 31 ms 14208 KB Output is correct
11 Correct 25 ms 14328 KB Output is correct
12 Correct 25 ms 14328 KB Output is correct
13 Correct 25 ms 14180 KB Output is correct
14 Correct 24 ms 14200 KB Output is correct
15 Correct 25 ms 14328 KB Output is correct
16 Correct 25 ms 14200 KB Output is correct
17 Correct 25 ms 14328 KB Output is correct
18 Correct 25 ms 14372 KB Output is correct
19 Correct 24 ms 14208 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 14584 KB Output is correct
2 Correct 134 ms 14712 KB Output is correct
3 Correct 151 ms 14708 KB Output is correct
4 Correct 147 ms 14784 KB Output is correct
5 Correct 129 ms 14712 KB Output is correct
6 Correct 133 ms 14712 KB Output is correct
7 Correct 148 ms 14688 KB Output is correct
8 Correct 196 ms 14840 KB Output is correct
9 Correct 244 ms 14960 KB Output is correct
10 Correct 258 ms 14840 KB Output is correct
11 Correct 264 ms 14968 KB Output is correct
12 Correct 267 ms 14960 KB Output is correct
13 Correct 235 ms 14868 KB Output is correct
14 Correct 234 ms 14696 KB Output is correct
15 Correct 149 ms 14712 KB Output is correct
16 Correct 141 ms 14712 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 14332 KB Output is correct
2 Correct 109 ms 14672 KB Output is correct
3 Correct 112 ms 14520 KB Output is correct
4 Correct 103 ms 14524 KB Output is correct
5 Correct 235 ms 14840 KB Output is correct
6 Correct 189 ms 14840 KB Output is correct
7 Correct 197 ms 14928 KB Output is correct
8 Correct 215 ms 14756 KB Output is correct
9 Correct 203 ms 14876 KB Output is correct
10 Correct 180 ms 14788 KB Output is correct
11 Correct 191 ms 14768 KB Output is correct
12 Correct 188 ms 14876 KB Output is correct
13 Correct 159 ms 14840 KB Output is correct
14 Correct 161 ms 14712 KB Output is correct
15 Correct 162 ms 14916 KB Output is correct
16 Correct 177 ms 14840 KB Output is correct
17 Correct 150 ms 14772 KB Output is correct
18 Correct 150 ms 14840 KB Output is correct
19 Correct 162 ms 14712 KB Output is correct
20 Correct 153 ms 14808 KB Output is correct
21 Correct 122 ms 14456 KB Output is correct
22 Correct 118 ms 14504 KB Output is correct
23 Correct 116 ms 14572 KB Output is correct