Submission #704423

#	Time	Username	Problem	Language	Result	Execution time	Memory
704423		ld_minh4354	Railway Trip 2 (JOI22_ho_t4)	C++17	27 / 100	2066 ms	31472 KiB

Main

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

#define int long long
#define fi first
#define se second
#define pb push_back
#define debug(x) cout<<#x<<": "<<x<<"\n"

struct node
{
	int s,e,m,val,lazy;
	node *l,*r;
	
	node(int S,int E)
	{
		s=S;e=E;m=(s+e)/2;
		val=S;lazy=1e9;
		
		if (s!=e)
		{
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void prop()
	{
		if (lazy==1e9) return;
		val=min(val,lazy);
		
		if (s!=e)
		{
			l->lazy = min(l->lazy,lazy);
			r->lazy = min(r->lazy,lazy);
		}
		lazy=1e9;
	}
	
	void update(int S,int E,int V)
	{
		if (s==S and e==E) lazy = min(lazy, V);
		else
		{
			if (E<=m) l->update(S,E,V);
			else if (S>m) r->update(S,E,V);
			else
			{
				l->update(S,m,V);r->update(m+1,E,V);
			}
			
			l->prop();r->prop();
			val=min(l->val,r->val);
		}
		
	}
	
	int query(int S,int E)
	{
		prop();
		
		if (s==S and e==E) return val;
		else if (E<=m) return l->query(S,E);
		else if (S>m) return r->query(S,E);
		else return min(l->query(S,m), r->query(m+1,E));
	}
}*lroot;

struct node2
{
	int s,e,m,val,lazy;
	node2 *l,*r;
	
	node2(int S,int E)
	{
		s=S;e=E;m=(s+e)/2;
		val=E;lazy=0;
		
		if (s!=e)
		{
			l=new node2(s,m);
			r=new node2(m+1,e);
		}
	}
	
	void prop()
	{
		if (lazy==0) return;
		val=max(val,lazy);
		
		if (s!=e)
		{
			l->lazy = max(l->lazy,lazy);
			r->lazy = max(r->lazy,lazy);
		}
		lazy=0;
	}
	
	void update(int S,int E,int V)
	{
		if (s==S and e==E) lazy = max(lazy, V);
		else
		{
			if (E<=m) l->update(S,E,V);
			else if (S>m) r->update(S,E,V);
			else
			{
				l->update(S,m,V);r->update(m+1,E,V);
			}
			
			l->prop();r->prop();
			val=max(l->val,r->val);
		}
		
	}
	
	int query(int S,int E)
	{
		prop();
		
		if (s==S and e==E) return val;
		else if (E<=m) return l->query(S,E);
		else if (S>m) return r->query(S,E);
		else return max(l->query(S,m), r->query(m+1,E));
	}
}*rroot;

signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//	freopen("input.000","r",stdin);
//	freopen("output.000","w",stdout);
//	srand((unsigned)time(NULL));
//	rand()
	
	int n,k,m,a[200005],b[200005],s,t,l,lnew,r,rnew,ans,i,q;
	bool stop;
	
	cin>>n>>k>>m;
	for (i=1;i<m+1;i++) cin>>a[i]>>b[i];
	
	lroot=new node(1,n);
	rroot=new node2(1,n);
	
	for (i=1;i<m+1;i++)
	if (a[i]<b[i]) rroot->update(a[i], min(a[i]+k-1,b[i]), b[i]);
	else lroot->update(max(a[i]-k+1,b[i]), a[i], b[i]);
	
	cin>>q;
	for (i=1;i<q+1;i++)
	{
		cin>>s>>t;
		ans=0;l=r=s;stop=false;
		while ((t<l or t>r) and !stop)
		{
			lnew=lroot->query(l,r);
			rnew=rroot->query(l,r);
			
			if (l==lnew and r==rnew) stop=true;
			l=lnew;r=rnew;ans++;
		}
		
		if (stop) cout<<"-1\n";else cout<<ans<<"\n";
	}
}

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