oj.uz

Submission #116581

# Submission time Handle Problem Language Result Execution time Memory
116581 2019-06-13T03:00:02 Z tmwilliamlin168 Railway Trip (JOI17_railway_trip) C++14
100 / 100
 1272 ms 460188 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;
			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 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 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 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 13036 KB Output is correct
4 Correct 35 ms 13012 KB Output is correct
5 Correct 34 ms 13048 KB Output is correct
6 Correct 105 ms 16248 KB Output is correct
7 Correct 907 ms 459256 KB Output is correct
8 Correct 610 ms 454720 KB Output is correct
9 Correct 477 ms 459360 KB Output is correct
10 Correct 241 ms 102396 KB Output is correct
11 Correct 614 ms 459384 KB Output is correct
12 Correct 374 ms 191556 KB Output is correct
13 Correct 275 ms 102392 KB Output is correct
14 Correct 674 ms 459324 KB Output is correct
15 Correct 379 ms 191688 KB Output is correct
16 Correct 243 ms 102392 KB Output is correct
17 Correct 474 ms 459468 KB Output is correct
18 Correct 461 ms 459384 KB Output is correct
19 Correct 584 ms 459564 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 13688 KB Output is correct
2 Correct 111 ms 13692 KB Output is correct
3 Correct 120 ms 13688 KB Output is correct
4 Correct 129 ms 13788 KB Output is correct
5 Correct 136 ms 13696 KB Output is correct
6 Correct 129 ms 13688 KB Output is correct
7 Correct 128 ms 13816 KB Output is correct
8 Correct 103 ms 13972 KB Output is correct
9 Correct 86 ms 13944 KB Output is correct
10 Correct 102 ms 13892 KB Output is correct
11 Correct 100 ms 13856 KB Output is correct
12 Correct 118 ms 13816 KB Output is correct
13 Correct 95 ms 13944 KB Output is correct
14 Correct 122 ms 13920 KB Output is correct
15 Correct 131 ms 13792 KB Output is correct
16 Correct 130 ms 13688 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1246 ms 459784 KB Output is correct
2 Correct 1272 ms 459904 KB Output is correct
3 Correct 457 ms 57464 KB Output is correct
4 Correct 670 ms 146704 KB Output is correct
5 Correct 677 ms 460048 KB Output is correct
6 Correct 739 ms 460152 KB Output is correct
7 Correct 560 ms 236236 KB Output is correct
8 Correct 450 ms 103032 KB Output is correct
9 Correct 949 ms 459896 KB Output is correct
10 Correct 740 ms 236024 KB Output is correct
11 Correct 596 ms 103076 KB Output is correct
12 Correct 944 ms 460152 KB Output is correct
13 Correct 725 ms 236156 KB Output is correct
14 Correct 1057 ms 460024 KB Output is correct
15 Correct 1137 ms 460188 KB Output is correct
16 Correct 1105 ms 460112 KB Output is correct
17 Correct 966 ms 460024 KB Output is correct
18 Correct 1037 ms 459860 KB Output is correct
19 Correct 1010 ms 459768 KB Output is correct
20 Correct 1034 ms 459768 KB Output is correct
21 Correct 628 ms 459500 KB Output is correct
22 Correct 652 ms 459608 KB Output is correct
23 Correct 1006 ms 459588 KB Output is correct