oj.uz

Submission #116535

# Submission time Handle Problem Language Result Execution time Memory
116535 2019-06-12T18:39:13 Z tmwilliamlin168 Railway Trip (JOI17_railway_trip) C++14
100 / 100
 1373 ms 459916 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]+(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 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 640 KB Output is correct
2 Correct 34 ms 12776 KB Output is correct
3 Correct 36 ms 12792 KB Output is correct
4 Correct 36 ms 12792 KB Output is correct
5 Correct 35 ms 12796 KB Output is correct
6 Correct 102 ms 15864 KB Output is correct
7 Correct 923 ms 459044 KB Output is correct
8 Correct 633 ms 454432 KB Output is correct
9 Correct 492 ms 459040 KB Output is correct
10 Correct 248 ms 102168 KB Output is correct
11 Correct 618 ms 459036 KB Output is correct
12 Correct 345 ms 191552 KB Output is correct
13 Correct 254 ms 102140 KB Output is correct
14 Correct 588 ms 459000 KB Output is correct
15 Correct 388 ms 191352 KB Output is correct
16 Correct 259 ms 102196 KB Output is correct
17 Correct 484 ms 459020 KB Output is correct
18 Correct 502 ms 459036 KB Output is correct
19 Correct 705 ms 459224 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 13480 KB Output is correct
2 Correct 114 ms 13364 KB Output is correct
3 Correct 131 ms 13304 KB Output is correct
4 Correct 125 ms 13304 KB Output is correct
5 Correct 290 ms 13304 KB Output is correct
6 Correct 130 ms 13408 KB Output is correct
7 Correct 131 ms 13308 KB Output is correct
8 Correct 94 ms 13476 KB Output is correct
9 Correct 84 ms 13432 KB Output is correct
10 Correct 102 ms 13404 KB Output is correct
11 Correct 97 ms 13560 KB Output is correct
12 Correct 102 ms 13432 KB Output is correct
13 Correct 110 ms 13408 KB Output is correct
14 Correct 130 ms 13432 KB Output is correct
15 Correct 135 ms 13560 KB Output is correct
16 Correct 151 ms 13388 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1254 ms 459384 KB Output is correct
2 Correct 1373 ms 459428 KB Output is correct
3 Correct 479 ms 57072 KB Output is correct
4 Correct 701 ms 146324 KB Output is correct
5 Correct 713 ms 459916 KB Output is correct
6 Correct 752 ms 459768 KB Output is correct
7 Correct 594 ms 235768 KB Output is correct
8 Correct 444 ms 102660 KB Output is correct
9 Correct 973 ms 459580 KB Output is correct
10 Correct 771 ms 235812 KB Output is correct
11 Correct 625 ms 102776 KB Output is correct
12 Correct 981 ms 459640 KB Output is correct
13 Correct 1033 ms 235620 KB Output is correct
14 Correct 1168 ms 459692 KB Output is correct
15 Correct 1128 ms 459600 KB Output is correct
16 Correct 1181 ms 459612 KB Output is correct
17 Correct 1100 ms 459680 KB Output is correct
18 Correct 1049 ms 459532 KB Output is correct
19 Correct 1058 ms 459732 KB Output is correct
20 Correct 1030 ms 459492 KB Output is correct
21 Correct 665 ms 459340 KB Output is correct
22 Correct 669 ms 459400 KB Output is correct
23 Correct 1028 ms 459360 KB Output is correct