oj.uz

Submission #411934

# Submission time Handle Problem Language Result Execution time Memory
411934 2021-05-26T09:43:32 Z errorgorn Railway Trip (JOI17_railway_trip) C++17
100 / 100
 1249 ms 322672 KB 
//雪花飄飄北風嘯嘯
//天地一片蒼茫

#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;
		}
	}
	
	rep(it,0,sz(edges)*3){
		ii curr=p[it][0];
		
		rep(x,0,20){
			if (curr.fi==-1) break;
			curr.se+=p[curr.fi][x].se;
			curr.fi=p[curr.fi][x].fi;
			p[it][x+1]=curr;
		}
	}
	
	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;
		rep(x,20,0){
			if (p[ca][x].fi!=-1 && arr[edges[p[ca][x].fi/3].se]<lo){
				da+=p[ca][x].se;
				ca=p[ca][x].fi;
			}
		}
		if (arr[edges[ca/3].se]<lo){
			da+=p[ca][0].se;
			ca=p[ca][0].fi;
		}
		rep(x,20,0){
			if (p[cb][x].fi!=-1 && arr[edges[p[cb][x].fi/3].fi]<lo){
				db+=p[cb][x].se;
				cb=p[cb][x].fi;
			}
		}
		if (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;
			
			rep(x,20,0){
				if (p[ca][x].fi!=-1 && arr[edges[p[ca][x].fi/3].fi]<=lo){
					da+=p[ca][x].se;
					ca=p[ca][x].fi;
				}
			}
			if (arr[edges[ca/3].fi]<=lo){
				da+=p[ca][0].se;
				ca=p[ca][0].fi;
			}
			rep(x,20,0){
				if (p[cb][x].fi!=-1 && arr[edges[p[cb][x].fi/3].se]<=lo){
					db+=p[cb][x].se;
					cb=p[cb][x].fi;
				}
			}
			if (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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 293880 KB Output is correct
2 Correct 129 ms 293848 KB Output is correct
3 Correct 138 ms 293832 KB Output is correct
4 Correct 132 ms 293896 KB Output is correct
5 Correct 146 ms 293896 KB Output is correct
6 Correct 135 ms 293796 KB Output is correct
7 Correct 130 ms 293832 KB Output is correct
8 Correct 152 ms 293800 KB Output is correct
9 Correct 131 ms 293836 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 294028 KB Output is correct
2 Correct 430 ms 317492 KB Output is correct
3 Correct 476 ms 318476 KB Output is correct
4 Correct 465 ms 319020 KB Output is correct
5 Correct 472 ms 319528 KB Output is correct
6 Correct 474 ms 319720 KB Output is correct
7 Correct 478 ms 321252 KB Output is correct
8 Correct 256 ms 311824 KB Output is correct
9 Correct 366 ms 315120 KB Output is correct
10 Correct 337 ms 313820 KB Output is correct
11 Correct 395 ms 315756 KB Output is correct
12 Correct 400 ms 315544 KB Output is correct
13 Correct 389 ms 315400 KB Output is correct
14 Correct 385 ms 315720 KB Output is correct
15 Correct 403 ms 315508 KB Output is correct
16 Correct 404 ms 315400 KB Output is correct
17 Correct 535 ms 319808 KB Output is correct
18 Correct 543 ms 319716 KB Output is correct
19 Correct 464 ms 322116 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 841 ms 318404 KB Output is correct
2 Correct 801 ms 317944 KB Output is correct
3 Correct 830 ms 318452 KB Output is correct
4 Correct 831 ms 318620 KB Output is correct
5 Correct 825 ms 318716 KB Output is correct
6 Correct 834 ms 318876 KB Output is correct
7 Correct 866 ms 318896 KB Output is correct
8 Correct 623 ms 314360 KB Output is correct
9 Correct 652 ms 312416 KB Output is correct
10 Correct 696 ms 312348 KB Output is correct
11 Correct 693 ms 312448 KB Output is correct
12 Correct 661 ms 312456 KB Output is correct
13 Correct 720 ms 312392 KB Output is correct
14 Correct 599 ms 312408 KB Output is correct
15 Correct 628 ms 312488 KB Output is correct
16 Correct 681 ms 313868 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 867 ms 321512 KB Output is correct
2 Correct 895 ms 321568 KB Output is correct
3 Correct 838 ms 320284 KB Output is correct
4 Correct 892 ms 320676 KB Output is correct
5 Correct 671 ms 312452 KB Output is correct
6 Correct 945 ms 315716 KB Output is correct
7 Correct 919 ms 315732 KB Output is correct
8 Correct 842 ms 314492 KB Output is correct
9 Correct 917 ms 316432 KB Output is correct
10 Correct 933 ms 316164 KB Output is correct
11 Correct 912 ms 315992 KB Output is correct
12 Correct 933 ms 316504 KB Output is correct
13 Correct 944 ms 316320 KB Output is correct
14 Correct 1136 ms 319276 KB Output is correct
15 Correct 1177 ms 320444 KB Output is correct
16 Correct 1249 ms 322472 KB Output is correct
17 Correct 981 ms 318148 KB Output is correct
18 Correct 977 ms 318268 KB Output is correct
19 Correct 980 ms 318336 KB Output is correct
20 Correct 876 ms 317852 KB Output is correct
21 Correct 952 ms 320200 KB Output is correct
22 Correct 967 ms 320156 KB Output is correct
23 Correct 928 ms 322672 KB Output is correct