oj.uz

답안 #116534

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
116534 2019-06-12T18:36:23 Z tmwilliamlin168 Railway Trip (JOI17_railway_trip) C++14
100 / 100
 1439 ms 403396 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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