Submission #867210

#	Time	Username	Problem	Language	Result	Execution time	Memory
867210		NotLinux	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	1851 ms	114856 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("O3,unroll-loops")
#pragma GCC target ("avx2,bmi,bmi2,lzcnt,popcnt")
const int N = 1e5 + 7;
const int M = 20;
const int inf = 1e9 + 7;
struct SEGT{//range update , range query
	vector < int > tree;
	int sz;
	SEGT(){
		sz = N;
		tree.assign(4 * sz , -inf);
	}
	inline int _query(int ind , int l , int r , int ql , int qr){
		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 qp , int qv){
		if(l == r){
			tree[ind] = max(tree[ind] , qv);
			return;
		}
		int mid = (l+r)/2;
		if(mid >= qp)_update(ind*2,l,mid,qp,qv);
		else _update(ind*2+1,mid+1,r,qp,qv);
		tree[ind] = max(tree[ind*2] , tree[ind*2+1]);
	}
	inline void update(int p ,int v){_update(1,1,sz,p,v);}
};
SEGT leftmost[M],rightmost[M];
void solve(){
	int n,k,m;cin >> n >> k >> m;
	int a[m],b[m];
	multiset < int > sol[N],sag[N],soldel[N],sagdel[N];
	for(int i = 1;i<N;i++){
		leftmost[0].update(i,-i);
		rightmost[0].update(i,i);
	}
	for(int i = 0;i<m;i++){
		cin >> a[i] >> b[i];
		if(a[i] < b[i]){
			sol[a[i]].insert(b[i]);
			soldel[a[i]+k-1].insert(b[i]);
		}
		else{
			sag[a[i]].insert(b[i]);
			sagdel[a[i]-k+1].insert(b[i]);
		}
	}
	multiset < int > cur;
	for(int i = 1;i<N;i++){
		for(auto itr : sol[i])cur.insert(itr);
		if(cur.size())rightmost[0].update(i,*--cur.end());
		for(auto itr : soldel[i])cur.extract(itr);
	}
	cur.clear();
	for(int i = N-1;i>=1;i--){
		for(auto itr : sag[i])cur.insert(itr);
		if(cur.size())leftmost[0].update(i,-*cur.begin());
		for(auto itr : sagdel[i])cur.extract(itr);
	}
	//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 ,  leftmost[i-1].query(lp , rp));
			rightmost[i].update(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: 11 / 11
• Subtask 4: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 13 / 13