Submission #902031

#	Time	Username	Problem	Language	Result	Execution time	Memory
902031		LCJLY	Railway Trip 2 (JOI22_ho_t4)	C++14	100 / 100	1757 ms	296532 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl; 
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<long long,long long>pii;

inline pii combine(const pii a,const pii b){
	return {min(a.first,b.first),max(a.second,b.second)};
}

struct node{
	int s,e,m;
	node *l,*r;
	pii v; //mini maxi
	int lazyMin,lazyMax;
	
	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1){
		v={s,e};
		lazyMin=INT_MAX;
		lazyMax=INT_MIN;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
			v=combine(l->v,r->v);
		}
	}
	
	void self_min(int x){
		v.first=min(v.first,x);
		lazyMin=min(lazyMin,x);
	}
	
	void self_max(int x){
		v.second=max(v.second,x);
		lazyMax=max(lazyMax,x);
	}
	
	void forceProp(){
		if(s==e) return;
		if(lazyMin!=INT_MAX){
			l->self_min(lazyMin); r->self_min(lazyMin);
			lazyMin=INT_MAX;
		}
		if(lazyMax!=INT_MIN){
			l->self_max(lazyMax); r->self_max(lazyMax);
			lazyMax=INT_MIN;
		}
	}
	
	void rangeUpd(int x, int y, pii c){
		if(x<=s&&y>=e){
			self_min(c.first);
			self_max(c.second);
			return;
		}
		forceProp();
		if(x<=m)l->rangeUpd(x,y,c);
		if(y>m)r->rangeUpd(x,y,c);
		v=combine(l->v,r->v);
	}
	
	pii query(int x, int y){
		if(x<=s&&y>=e){
			return v;
		}
		forceProp();
		if(y<=m)return l->query(x,y);
		if(x>m)return r->query(x,y);
		return combine(l->query(x,m),r->query(m+1,y));
	}
}*st[17];

void solve(){	
	int n,k;
	cin >> n >> k;
	int m;
	cin >> m;
	
	for(int x=0;x<17;x++){
		st[x]=new node(0,n+5);
	}
	
	int temp,temp2;
	for(int x=0;x<m;x++){
		cin >> temp >> temp2;
		if(temp<temp2){
			int hold=min(temp+k-1,temp2);
			st[0]->rangeUpd(temp,hold,{temp2,temp2});
		}
		else{
			int hold=max(temp-k+1,temp2);
			st[0]->rangeUpd(hold,temp,{temp2,temp2});
		}
	}
	
	pii two[17][n+5];
	for(int bit=0;bit<17;bit++){
		for(int x=0;x<=n;x++){
			if(bit==0){
				two[bit][x]=st[bit]->query(x,x);
			}
			else{
				two[bit][x]=st[bit-1]->query(two[bit-1][x].first,two[bit-1][x].second);
				st[bit]->rangeUpd(x,x,two[bit][x]);
				//show2(bit,bit,x,x);
				//show2(l,two[bit][x].first,r,two[bit][x].second);
				//show2(prev,two[bit-1][x].first,prev,two[bit-1][x].second);
			}
		}
	}
	
	int q;
	cin >> q;
	
	for(int x=0;x<q;x++){
		cin >> temp >> temp2;
		
		if(temp<temp2){
			int l=temp;
			int r=temp;
			
			int ans=0;
			for(int bit=16;bit>=0;bit--){
				pii hold=st[bit]->query(l,r);
				if(hold.second<temp2){
					ans+=1<<bit;
					l=hold.first;
					r=hold.second;
				}
			}
			
			if(st[0]->query(l,r).second<temp2){
				cout << -1 << "\n";
			}
			else{
				cout << ans+1 << "\n";
			}
		}
		else{
			int l=temp;
			int r=temp;
			
			int ans=0;
			for(int bit=16;bit>=0;bit--){
				pii hold=st[bit]->query(l,r);
				if(hold.first>temp2){
					ans+=1<<bit;
					l=hold.first;
					r=hold.second;
				}
			}
			
			if(st[0]->query(l,r).first>temp2){
				cout << -1 << "\n";
			}
			else{
				cout << ans+1 << "\n";
			}
		}
	}
}	
 
int32_t main(){										
	ios::sync_with_stdio(0);	
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		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