oj.uz

Submission #116588

# Submission time Handle Problem Language Result Execution time Memory
116588 2019-06-13T03:18:41 Z tmwilliamlin168 Railway Trip (JOI17_railway_trip) C++14
100 / 100
 1421 ms 459900 KB 
#include <bits/stdc++.h>
using namespace std;

#define d1 array<int, 2>
#define d2 array<d1, 2>

const int mxN=1e5, BS=350;
int n, k, q, l[17][mxN], ln1[mxN], ln2[mxN], ld[mxN], rn1[mxN], rn2[mxN], rd[mxN];
d1 p[mxN];
d2 nxts[mxN], nxtb[(mxN-1)/BS+1][mxN];

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

	cin >> n >> k >> q;
	for(int i=0; i<n; ++i)
		cin >> l[0][i], --l[0][i];
	for(int i=1; i<17; ++i)
		for(int j=0; j<=n-(1<<i); ++j)
			l[i][j]=max(l[i-1][j], l[i-1][j+(1<<i-1)]);
	for(int i=0; i<n; ++i) {
		ln1[i]=ln2[i]=i-1;
		while(~ln1[i]&&l[0][ln1[i]]<=l[0][i])
			ln1[i]=ln1[ln1[i]];
		while(~ln2[i]&&l[0][ln2[i]]<l[0][i])
			ln2[i]=ln2[ln2[i]];
		if(~ln2[i])
			ld[i]=ld[ln2[i]]+1;
	}
	for(int i=n-1; ~i; --i) {
		rn1[i]=rn2[i]=i+1;
		while(rn1[i]<n&&l[0][rn1[i]]<=l[0][i])
			rn1[i]=rn1[rn1[i]];
		while(rn2[i]<n&&l[0][rn2[i]]<l[0][i])
			rn2[i]=rn2[rn2[i]];
		if(rn2[i]<n) {
			rd[i]=rd[rn2[i]]+1;
			nxts[i]={{{ld[i]-ld[ln1[i]], ln1[i]}, {rd[i]-rd[rn1[i]], rn1[i]}}};
		}
		p[i]={l[0][i], i};
	}
	sort(p, p+n);
	auto cmb=[](d2 a, d2 b, d2 c) {
		if(!b[1][0])
			b[1][0]=n;
		if(!c[0][0])
			c[0][0]=n;
		d2 r={min(d1{b[0][0]+a[0][0], b[0][1]}, d1{c[0][0]+a[1][0], c[0][1]}), min(d1{b[1][0]+a[0][0], b[1][1]}, d1{c[1][0]+a[1][0], c[1][1]})};
		r[0][0]=min(r[1][0]+1, r[0][0]);
		r[1][0]=min(r[0][0]+1, r[1][0]);
		return r;
	};
	auto qry=[&](int i, int t, int ex=0) {
		d2 r=nxtb[t/BS][i];
		for(int j=max(t/BS*BS, l[0][i]); j<t+ex; ++j) {
			int cl=r[0][1], cr=r[1][1];
			r=cmb(r, l[0][cl]>j?d2{{{0, cl}, {0, cl}}}:nxts[cl], l[0][cr]>j?d2{{{0, cr}, {0, cr}}}:nxts[cr]);
		}
		return r;
	};
	for(int i=0; i<k; i+=BS) {
		for(int j1=n-1; ~j1; --j1) {
			int j2=p[j1][1];
			nxtb[i/BS][j2]=l[0][j2]>=i?d2{{{0, j2}, {0, j2}}}:(nxtb[i/BS-1][j2][0][0]?cmb(nxtb[i/BS-1][j2], nxtb[i/BS][nxtb[i/BS-1][j2][0][1]], nxtb[i/BS][nxtb[i/BS-1][j2][1][1]]):qry(j2, i-1, 1));
		}
	}
	for(int a, b; q--; ) {
		cin >> a >> b, --a, --b;
		if(a>b)
			swap(a, b);
		int c=31-__builtin_clz(b-a+1), m=max(l[c][a], l[c][b-(1<<c)+1]);
		d2 da=qry(a, m), db=qry(b, m);
		int ans=da[1][0]+db[0][0]+ld[db[0][1]]-ld[da[1][1]];
		if(m+1<k) {
			da=qry(a, m+1), db=qry(b, m+1);
			ans=min(da[0][0]+db[1][0]+1, ans);
		}
		cout << ans-1 << "\n";
	}
}

Subtask #1
5.0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 35 ms 12920 KB Output is correct
3 Correct 35 ms 13048 KB Output is correct
4 Correct 33 ms 13048 KB Output is correct
5 Correct 33 ms 13048 KB Output is correct
6 Correct 92 ms 16120 KB Output is correct
7 Correct 878 ms 459256 KB Output is correct
8 Correct 602 ms 454472 KB Output is correct
9 Correct 490 ms 459384 KB Output is correct
10 Correct 251 ms 102320 KB Output is correct
11 Correct 589 ms 459384 KB Output is correct
12 Correct 334 ms 191624 KB Output is correct
13 Correct 242 ms 102384 KB Output is correct
14 Correct 575 ms 459272 KB Output is correct
15 Correct 337 ms 191628 KB Output is correct
16 Correct 250 ms 102372 KB Output is correct
17 Correct 474 ms 459256 KB Output is correct
18 Correct 844 ms 459220 KB Output is correct
19 Correct 632 ms 459052 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 13304 KB Output is correct
2 Correct 110 ms 13440 KB Output is correct
3 Correct 143 ms 13432 KB Output is correct
4 Correct 148 ms 13432 KB Output is correct
5 Correct 127 ms 13432 KB Output is correct
6 Correct 132 ms 13304 KB Output is correct
7 Correct 127 ms 13364 KB Output is correct
8 Correct 94 ms 13432 KB Output is correct
9 Correct 92 ms 13532 KB Output is correct
10 Correct 96 ms 13620 KB Output is correct
11 Correct 111 ms 13472 KB Output is correct
12 Correct 115 ms 13536 KB Output is correct
13 Correct 99 ms 13512 KB Output is correct
14 Correct 130 ms 13440 KB Output is correct
15 Correct 156 ms 13420 KB Output is correct
16 Correct 141 ms 13332 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1306 ms 459500 KB Output is correct
2 Correct 1421 ms 459512 KB Output is correct
3 Correct 479 ms 57148 KB Output is correct
4 Correct 667 ms 146368 KB Output is correct
5 Correct 707 ms 459744 KB Output is correct
6 Correct 722 ms 459824 KB Output is correct
7 Correct 562 ms 235768 KB Output is correct
8 Correct 450 ms 102740 KB Output is correct
9 Correct 939 ms 459768 KB Output is correct
10 Correct 737 ms 235768 KB Output is correct
11 Correct 614 ms 102776 KB Output is correct
12 Correct 931 ms 459800 KB Output is correct
13 Correct 736 ms 235700 KB Output is correct
14 Correct 1154 ms 459788 KB Output is correct
15 Correct 1177 ms 459768 KB Output is correct
16 Correct 1176 ms 459724 KB Output is correct
17 Correct 958 ms 459896 KB Output is correct
18 Correct 1020 ms 459900 KB Output is correct
19 Correct 983 ms 459640 KB Output is correct
20 Correct 967 ms 459608 KB Output is correct
21 Correct 636 ms 459420 KB Output is correct
22 Correct 802 ms 459400 KB Output is correct
23 Correct 1008 ms 459396 KB Output is correct