Submission #411933

#	Time	Username	Problem	Language	Result	Execution time	Memory
411933		errorgorn	Railway Trip (JOI17_railway_trip)	C++17	45 / 100	2102 ms	322464 KiB

railway_trip

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

struct node{
	int s,e,m;
	int mx=0;
	node *l,*r;
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void update(int i,int j){
		if (s==e) mx=j;
		else{
			if (i<=m) l->update(i,j);
			else r->update(i,j);
			
			mx=max(l->mx,r->mx);
		}
	}
	
	int query(int i,int j){
		if (s==i && e==j) return mx;
		else if (j<=m) return l->query(i,j);
		else if (m<i) return r->query(i,j);
		else return max(l->query(i,m),r->query(m+1,j));
	}
} *root=new node(0,100005);

int n,k,q;
int arr[100005];
vector<int> pos[100005];

int l[100005];
int r[100005];

int lp[100005];
int rp[100005];

int w[100005];

vector<ii> edges;
map<ii,int> id; //map edges to an id
//each id has 3 variants
//0 1
//0 0
//1 0

ii p[900005][20];

void process(){
	vector<int> stk;
	
	stk={};
	rep(x,1,n+1){
		while (!stk.empty() && arr[stk.back()]<arr[x]) stk.pob();
		if (!stk.empty()) l[x]=stk.back();
		
		stk.pub(x);
	}
	
	stk={};
	rep(x,n+1,1){
		while (!stk.empty() && arr[stk.back()]<arr[x]) stk.pob();
		if (!stk.empty()) r[x]=stk.back();
		
		stk.pub(x);
	}
	
	stk={};
	rep(x,1,n+1){
		while (!stk.empty() && arr[stk.back()]<=arr[x]) stk.pob();
		if (!stk.empty()) lp[x]=stk.back();
		
		stk.pub(x);
	}
	
	stk={};
	rep(x,n+1,1){
		while (!stk.empty() && arr[stk.back()]<=arr[x]) stk.pob();
		if (!stk.empty()) rp[x]=stk.back();
		
		stk.pub(x);
	}
}

int nquery(int val,int l,int r){
	return ub(all(pos[val]),r)-lb(all(pos[val]),l);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>k>>q;
	rep(x,1,n+1){
		cin>>arr[x];
		pos[arr[x]].pub(x);
		root->update(x,arr[x]);
	}
	arr[0]=1e9;
	
	process();
	
	rep(x,1,n+1) edges.pub(ii(x,x));
	rep(x,1,n+1) if (r[x] && arr[r[x]]>arr[x]) edges.pub(ii(x,r[x]));
	rep(x,1,n+1) if (l[x] && arr[l[x]]>=arr[x]) edges.pub(ii(l[x],x));
	
	sort(all(edges),[](ii i,ii j){
		return (i.se-i.fi)>(j.se-j.fi);
	});
	
	memset(p,-1,sizeof(p));
	
	rep(x,0,sz(edges)){
		id[edges[x]]=x*3;
		//cout<<edges[x].fi<<" "<<edges[x].se<<" "<<x*3<<endl;
		
		int l2=edges[x].fi,r2=edges[x].se;
		if (arr[l2]==k && arr[r2]==k) continue;
		if (arr[l2]<arr[r2]) l2=lp[l2];
		else if (arr[r2]<arr[l2]) r2=rp[r2];
		else l2=lp[l2],r2=rp[r2];
		
		int ldist=nquery(arr[edges[x].fi],l2+1,edges[x].fi);
		int rdist=nquery(arr[edges[x].se],edges[x].se,r2-1);
		
		//cout<<ldist<<" "<<rdist<<endl;
		
		int pval=id[ii(l2,r2)];
		rep(z,0,3){
			int lc=0,rc=0;
			if (z==0) rc=1;
			if (z==2) lc=1;
			
			lc+=ldist,rc+=rdist;
			
			ii res;
			if (lc==rc) res.fi=pval+1;
			else if (lc<rc) res.fi=pval+0;
			else res.fi=pval+2;
			res.se=min(lc,rc);
			
			//cout<<"parent: "<<x*3+z<<" "<<res.fi<<endl;
			
			p[x*3+z][0]=res;
		}
	}
	
	int a,b;
	while (q--){
		cin>>a>>b;
		if (a>b) swap(a,b);
		int lo=-1;
		if (a+1!=b) lo=root->query(a+1,b-1);
		
		if (min(arr[a],arr[b])>lo){
			cout<<"0"<<endl;
			continue;
		}
		
		int ca=id[ii(a,a)]+1,cb=id[ii(b,b)]+1;
		int da=0,db=0;
		
		int ans;
		while (arr[edges[ca/3].se]<lo){
			da+=p[ca][0].se;
			ca=p[ca][0].fi;
		}
		while (arr[edges[cb/3].fi]<lo){
			db+=p[cb][0].se;
			cb=p[cb][0].fi;
		}
		
		ans=da+db+nquery(lo,edges[ca/3].se+1,edges[cb/3].fi-1);
		if (ca%3==0) ans++;
		if (cb%3==2) ans++;
		
		if (lo!=k){
			ca=id[ii(a,a)]+1,cb=id[ii(b,b)]+1;
			da=0,db=0;
			
			while (arr[edges[ca/3].fi]<=lo){
				da+=p[ca][0].se;
				ca=p[ca][0].fi;
			}
			while (arr[edges[cb/3].se]<=lo){
				db+=p[cb][0].se;
				cb=p[cb][0].fi;
			}
			
			int temp=da+db;
			if (ca%3==2) temp++;
			if (cb%3==0) temp++;
			
			ans=min(ans,temp);
		}
		
		cout<<ans<<endl;
	}
}

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