Submission #928282

#	Time	Username	Problem	Language	Result	Execution time	Memory
928282		pcc	Railway Trip 2 (JOI22_ho_t4)	C++17	27 / 100	2068 ms	22596 KiB

Main

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


#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 1e5+10;

int N,M,K,Q;
pii range[mxn],segtree[mxn*4];
vector<int> lop[mxn],rop[mxn];

void build(int now,int l,int r){
	if(l == r){
		segtree[now] = range[l];
		return;
	}
	int mid = (l+r)>>1;
	build(now*2+1,l,mid);
	build(now*2+2,mid+1,r);
	segtree[now].fs = min(segtree[now*2+1].fs,segtree[now*2+2].fs);
	segtree[now].sc = max(segtree[now*2+1].sc,segtree[now*2+2].sc);
}
pii getval(int now,int l,int r,int s,int e){
	if(l>=s&&e>=r)return segtree[now];
	int mid = (l+r)>>1;
	if(mid>=e)return getval(now*2+1,l,mid,s,e);
	else if(mid<s)return getval(now*2+2,mid+1,r,s,e);
	else{
		auto ta = getval(now*2+1,l,mid,s,e),tb = getval(now*2+2,mid+1,r,s,e);
		return make_pair(min(ta.fs,tb.fs),max(ta.sc,tb.sc));
	}
}

void solve(){
	int s,e;
	cin>>s>>e;
	pii now = {s,s};
	int ans = 0;
	while(now.fs>e||now.sc<e){
		ans++;
		auto nxt = getval(0,1,N,now.fs,now.sc);
		if(nxt.fs == now.fs&&nxt.sc == now.sc)break;
		now = nxt;
	}
	cout<<(now.fs>e||now.sc<e?-1:ans)<<'\n';
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>K>>M;
	for(int i = 0;i<M;i++){
		int a,b;
		cin>>a>>b;
		if(a<=b){
			int e = min(b+1,a+K);
			rop[a].push_back(b);
			rop[e].push_back(-b);
		}
		else{
			int e = max(b-1,a-K);
			lop[a].push_back(b);
			lop[e].push_back(-b);
		}
	}
	for(int i = 1;i<=N;i++)range[i].fs = range[i].sc = i;
	multiset<int> st;
	for(int i = 1;i<=N;i++){
		for(auto &j:rop[i]){
			if(j>0)st.insert(j);
			else st.erase(st.find(-j));
		}
		if(!st.empty())range[i].sc = *st.rbegin();
	}

	st.clear();
	for(int i = N;i>=1;i--){
		for(auto &j:lop[i]){
			if(j>0)st.insert(j);
			else st.erase(st.find(-j));
		}
		if(!st.empty())range[i].fs = *st.begin();
	}
	build(0,1,N);
	cin>>Q;
	while(Q--)solve();
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 0 / 25
• Subtask 5: 0 / 35
• Subtask 6: 0 / 13