Submission #867202

#	Time	Username	Problem	Language	Result	Execution time	Memory
867202		NotLinux	Railway Trip 2 (JOI22_ho_t4)	C++17	16 / 100	2062 ms	256640 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 7;
const int M = 20;
const int inf = 1e9 + 7;
struct SEGT{//range update , range query
	vector < int > tree , psh;
	int sz;
	SEGT(){
		sz = N;
		tree.assign(4 * sz , -inf);
		psh.assign(4 * sz, -inf);
	}
	inline void push(int ind , int l , int r){
		tree[ind] = max(tree[ind] , psh[ind]);
		if(l == r)return;
		psh[ind*2] = max(psh[ind*2] , psh[ind]);
		psh[ind*2+1] = max(psh[ind*2+1] , psh[ind]);
		psh[ind] = -inf;
	}
	inline int _query(int ind , int l , int r , int ql , int qr){
		push(ind,l,r);
		if(l >= ql and r <= qr)return tree[ind];
		else if(l > qr or r < ql)return -inf;
		int mid = (l+r)/2;
		return max(_query(ind*2,l,mid,ql,qr) , _query(ind*2+1,mid+1,r,ql,qr));
	}
	inline int query(int l , int r){return _query(1,1,sz,l,r);}
	inline void _update(int ind , int l , int r , int ql , int qr , int qp){
		push(ind,l,r);
		if(l >= ql and r <= qr){
			psh[ind] = max(psh[ind] , qp);
			push(ind,l,r);
			return;
		}
		else if(l > qr or r < ql)return;
		int mid = (l+r)/2;
		_update(ind*2,l,mid,ql,qr,qp);
		_update(ind*2+1,mid+1,r,ql,qr,qp);
		tree[ind] = max(tree[ind*2] , tree[ind*2+1]);
	}
	inline void update(int l , int r ,int p){_update(1,1,sz,l,r,p);}
};
SEGT leftmost[M],rightmost[M];
void solve(){
	int n,k,m;cin >> n >> k >> m;
	int a[m],b[m];
	for(int i = 1;i<=n;i++){
		leftmost[0].update(i,i,-i);
		rightmost[0].update(i,i,i);
	}
	for(int i = 0;i<m;i++){
		cin >> a[i] >> b[i];
		if(a[i] < b[i]){
			rightmost[0].update(a[i] , a[i]+k-1 , b[i]);
		}
		else{
			leftmost[0].update(a[i]-k+1 , a[i] , -b[i]);
		}
	}
	//cout << "leftmost : ";for(int i = 1;i<=n;i++)cout << leftmost[0].query(i,i) << " ";cout << endl;
	//cout << "rightmost : ";for(int i = 1;i<=n;i++)cout << rightmost[0].query(i,i) << " ";cout << endl;
	for(int i = 1;i<M;i++){
		for(int j = 1;j<=n;j++){
			int lp = -leftmost[i-1].query(j , j);
			int rp = rightmost[i-1].query(j , j);
			leftmost[i].update(j , j  ,  leftmost[i-1].query(lp , rp));
			rightmost[i].update(j , j , rightmost[i-1].query(lp , rp));
		}
	}
	int q;cin >> q;
	while(q--){
		int s,t,ans=0;cin >> s >> t;
		if(s == t){
			cout << 0 << endl;
			return;
		}
		pair < int , int > cur = {s,s};
		bool bl = 1;
		for(int i = M-1;i>=0;i--){
			pair < int , int > ncur = {-leftmost[i].query(cur.first,cur.second) , rightmost[i].query(cur.first,cur.second)};
			if(ncur.second < t or ncur.first > t){//al
				cur = ncur;
				ans += 1 << i;
			}
			else bl = 0;
		}
		cout << (bl?-1:ans+1) << '\n';
	}
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

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