Submission #116534

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
116534	2019-06-12T18:36:23 Z	tmwilliamlin168	Railway Trip (JOI17_railway_trip)	C++14	100 / 100	1439 ms	403396 KB

railway_trip

#include <bits/stdc++.h>
using namespace std;

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

const int mxN=1e5, BS=400;
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];
		p[i]={l[0][i], i};
	}
	sort(p, p+n);
	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;
		if(l[0][i]<k-1)
			nxts[i]={{{ld[i]-ld[ln1[i]], ln1[i]}, {rd[i]-rd[rn1[i]], rn1[i]}}};
	}
	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]+(l[0][db[1][1]]<l[0][da[0][1]]?ld[db[1][1]]-ld[da[0][1]]:rd[da[0][1]]-rd[db[1][1]]), ans);
		}
		cout << ans-1 << "\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	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	2 ms	512 KB	Output is correct
7	Correct	2 ms	512 KB	Output is correct
8	Correct	2 ms	512 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	5 ms	640 KB	Output is correct
2	Correct	71 ms	12708 KB	Output is correct
3	Correct	35 ms	12792 KB	Output is correct
4	Correct	35 ms	12796 KB	Output is correct
5	Correct	36 ms	12796 KB	Output is correct
6	Correct	117 ms	16004 KB	Output is correct
7	Correct	932 ms	402748 KB	Output is correct
8	Correct	597 ms	397996 KB	Output is correct
9	Correct	451 ms	402628 KB	Output is correct
10	Correct	240 ms	89464 KB	Output is correct
11	Correct	584 ms	402552 KB	Output is correct
12	Correct	373 ms	167808 KB	Output is correct
13	Correct	249 ms	89464 KB	Output is correct
14	Correct	581 ms	402724 KB	Output is correct
15	Correct	352 ms	167876 KB	Output is correct
16	Correct	267 ms	89504 KB	Output is correct
17	Correct	427 ms	402760 KB	Output is correct
18	Correct	452 ms	402684 KB	Output is correct
19	Correct	556 ms	402668 KB	Output is correct

Subtask #3

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	125 ms	13196 KB	Output is correct
2	Correct	114 ms	13220 KB	Output is correct
3	Correct	127 ms	13304 KB	Output is correct
4	Correct	123 ms	13176 KB	Output is correct
5	Correct	123 ms	13292 KB	Output is correct
6	Correct	110 ms	13220 KB	Output is correct
7	Correct	115 ms	13176 KB	Output is correct
8	Correct	82 ms	13432 KB	Output is correct
9	Correct	78 ms	13432 KB	Output is correct
10	Correct	94 ms	13304 KB	Output is correct
11	Correct	94 ms	13384 KB	Output is correct
12	Correct	99 ms	13304 KB	Output is correct
13	Correct	107 ms	13356 KB	Output is correct
14	Correct	129 ms	13432 KB	Output is correct
15	Correct	143 ms	13176 KB	Output is correct
16	Correct	150 ms	13304 KB	Output is correct

Subtask #4

55.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1321 ms	403148 KB	Output is correct
2	Correct	1439 ms	402988 KB	Output is correct
3	Correct	653 ms	50812 KB	Output is correct
4	Correct	913 ms	129012 KB	Output is correct
5	Correct	615 ms	403148 KB	Output is correct
6	Correct	749 ms	403360 KB	Output is correct
7	Correct	577 ms	207608 KB	Output is correct
8	Correct	473 ms	90104 KB	Output is correct
9	Correct	996 ms	403236 KB	Output is correct
10	Correct	822 ms	207648 KB	Output is correct
11	Correct	667 ms	89924 KB	Output is correct
12	Correct	962 ms	403328 KB	Output is correct
13	Correct	768 ms	207420 KB	Output is correct
14	Correct	1101 ms	403384 KB	Output is correct
15	Correct	1048 ms	403216 KB	Output is correct
16	Correct	1060 ms	403396 KB	Output is correct
17	Correct	1117 ms	403220 KB	Output is correct
18	Correct	1057 ms	403272 KB	Output is correct
19	Correct	1101 ms	403152 KB	Output is correct
20	Correct	1056 ms	403044 KB	Output is correct
21	Correct	603 ms	402908 KB	Output is correct
22	Correct	608 ms	403044 KB	Output is correct
23	Correct	1149 ms	402932 KB	Output is correct