oj.uz

Submission #116578

# Submission time Handle Problem Language Result Execution time Memory
116578 2019-06-13T02:16:52 Z tmwilliamlin168 Railway Trip (JOI17_railway_trip) C++14
100 / 100
 1336 ms 461444 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];
		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]+1, ans);
		}
		cout << ans-1 << "\n";
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 2 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 33 ms 12920 KB Output is correct
3 Correct 35 ms 13012 KB Output is correct
4 Correct 35 ms 13048 KB Output is correct
5 Correct 35 ms 13048 KB Output is correct
6 Correct 98 ms 16248 KB Output is correct
7 Correct 938 ms 459656 KB Output is correct
8 Correct 702 ms 454576 KB Output is correct
9 Correct 501 ms 459484 KB Output is correct
10 Correct 244 ms 102556 KB Output is correct
11 Correct 619 ms 459728 KB Output is correct
12 Correct 372 ms 191756 KB Output is correct
13 Correct 267 ms 102520 KB Output is correct
14 Correct 652 ms 459592 KB Output is correct
15 Correct 416 ms 191992 KB Output is correct
16 Correct 262 ms 102524 KB Output is correct
17 Correct 498 ms 459468 KB Output is correct
18 Correct 508 ms 459724 KB Output is correct
19 Correct 619 ms 459516 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 14568 KB Output is correct
2 Correct 130 ms 14680 KB Output is correct
3 Correct 122 ms 14684 KB Output is correct
4 Correct 141 ms 14620 KB Output is correct
5 Correct 134 ms 14644 KB Output is correct
6 Correct 128 ms 14712 KB Output is correct
7 Correct 137 ms 14712 KB Output is correct
8 Correct 82 ms 14712 KB Output is correct
9 Correct 86 ms 14712 KB Output is correct
10 Correct 104 ms 14712 KB Output is correct
11 Correct 106 ms 14716 KB Output is correct
12 Correct 99 ms 14664 KB Output is correct
13 Correct 91 ms 14712 KB Output is correct
14 Correct 136 ms 14664 KB Output is correct
15 Correct 152 ms 14640 KB Output is correct
16 Correct 141 ms 14584 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1166 ms 460916 KB Output is correct
2 Correct 1336 ms 460836 KB Output is correct
3 Correct 462 ms 58616 KB Output is correct
4 Correct 676 ms 147832 KB Output is correct
5 Correct 679 ms 461012 KB Output is correct
6 Correct 731 ms 461312 KB Output is correct
7 Correct 592 ms 237432 KB Output is correct
8 Correct 490 ms 104184 KB Output is correct
9 Correct 933 ms 461176 KB Output is correct
10 Correct 758 ms 237272 KB Output is correct
11 Correct 616 ms 104244 KB Output is correct
12 Correct 982 ms 461196 KB Output is correct
13 Correct 761 ms 237576 KB Output is correct
14 Correct 1093 ms 461208 KB Output is correct
15 Correct 1171 ms 461236 KB Output is correct
16 Correct 1122 ms 461176 KB Output is correct
17 Correct 1029 ms 461444 KB Output is correct
18 Correct 1044 ms 461412 KB Output is correct
19 Correct 1105 ms 461364 KB Output is correct
20 Correct 1018 ms 461272 KB Output is correct
21 Correct 646 ms 460996 KB Output is correct
22 Correct 733 ms 461164 KB Output is correct
23 Correct 1018 ms 461176 KB Output is correct