Submission #116597

#	Time	Username	Problem	Language	Result	Execution time	Memory
116597		tmwilliamlin168	Railway Trip (JOI17_railway_trip)	C++14	0 / 100	500 ms	74792 KiB

railway_trip

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

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

const int mxN=1e5, mxM=3*mxN-4;
int n, k, q, l[mxN], ln1[mxN], ln2[mxN], ld[mxN], rn1[mxN], rn2[mxN], rd[mxN], m, d[mxM], x[mxM];
d1 p[mxN];
d2 anc[mxM][17];
unordered_map<int, int> mp[mxN];

d2 cmb(d2 a, d2 b, d2 c) {
	if(b[0][1]==-1)
		return b;
	if(c[0][1]==-1)
		return 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]})};
	return r;
}

int bld(int i, int j) {
	if(mp[i].find(j)!=mp[i].end())
		return mp[i][j];
	int u=mp[i][j]=m++;
	x[u]=i;
	//cout << "node " << u << " " << i << " " << j << endl;
	if(j<k) {
		int nl, nr;
		if(j>=l[i]) {
			nl=bld(ln1[i], min(l[ln1[i]], l[rn1[i]]));
			nr=bld(rn1[i], min(l[ln1[i]], l[rn1[i]]));
		} else
			nl=nr=(++mp[i].find(j))->second;
		//cout << "n " << nl << " " << nr << endl;
		anc[u][0]={{{ld[i]-ld[x[nl]], nl}, {rd[i]-rd[x[nr]], nr}}};
		anc[u][0][0][0]=min(anc[u][0][1][0]+1, anc[u][0][0][0]);
		anc[u][0][1][0]=min(anc[u][0][0][0]+1, anc[u][0][1][0]);
		d[u]=d[anc[u][0][0][1]]+1;
	} else
		anc[u][0][0][1]=-1;
	for(int k=1; k<17; ++k)
		anc[u][k]=~anc[u][k-1][0][1]?cmb(anc[u][k-1], anc[anc[u][k-1][0][1]][k-1], anc[anc[u][k-1][1][1]][k-1]):anc[u][k-1];
	return u;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k >> q;
	for(int i=0; i<n; ++i)
		cin >> l[i];
	for(int i=0; i<n; ++i) {
		ln1[i]=ln2[i]=i-1;
		while(~ln1[i]&&l[ln1[i]]<=l[i])
			ln1[i]=ln1[ln1[i]];
		while(~ln2[i]&&l[ln2[i]]<l[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[rn1[i]]<=l[i])
			rn1[i]=rn1[rn1[i]];
		while(rn2[i]<n&&l[rn2[i]]<l[i])
			rn2[i]=rn2[rn2[i]];
		if(rn2[i]<n)
			rd[i]=rd[rn2[i]]+1;
		p[i]={l[i], i};
	}
	sort(p, p+n);
	for(int i=n-1; ~i; --i)
		bld(p[i][1], p[i][0]);
	//auto dbg=[](d2 a) {
		//cout << a[0][0] << " " << a[0][1] << " " << a[1][0] << " " << a[1][1] << endl;
	//};
	for(int a, b, ans; q--; ) {
		cin >> a >> b, --a, --b;
		a=mp[a][l[a]];
		b=mp[b][l[b]];
		if(d[a]<d[b])
			swap(a, b);
		d2 da{{{0, a}, {0, a}}}, db{{{0, b}, {0, b}}};
		for(int i=16; ~i; --i)
			if(d[da[0][1]]-(1<<i)>=d[b])
				da=cmb(da, anc[da[0][1]][i], anc[da[1][1]][i]);
		//dbg(da);
		if(da[0][1]^b&&da[1][1]^b) {
			for(int i=16; ~i; --i) {
				d2 na=cmb(da, anc[da[0][1]][i], anc[da[1][1]][i]), nb=cmb(db, anc[db[0][1]][i], anc[db[1][1]][i]);
				if(na[0][1]^nb[0][1]) {
					da=na;
					db=nb;
				}
			}
			if(x[da[0][1]]>x[db[0][1]])
				swap(da, db);
			ans=da[1][0]+db[0][0]+ld[x[db[0][1]]]-ld[x[da[1][1]]];
			da=cmb(da, anc[da[0][1]][0], anc[da[1][1]][0]), db=cmb(db, anc[db[0][1]][0], anc[db[1][1]][0]);
			if(~da[0][1])
				ans=min(da[0][0]+db[1][0]+1, ans);
		} else if(da[0][1]^b)
			ans=da[1][0];
		else
			ans=da[0][0];
		cout << ans-1 << "\n";
	}
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55