Submission #638718

#	Time	Username	Problem	Language	Result	Execution time	Memory
638718		jamezzz	Railway Trip 2 (JOI22_ho_t4)	C++17	27 / 100	2075 ms	15640 KiB

Main

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

#define fi first
#define se second
#define sf scanf
#define pf printf
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
 
#define maxn 100005
#define INF 1023456789

int n,k,m,q,mn[20][maxn],mx[20][maxn];

inline int getmn(int l,int r){
	l=max(1,l),r=min(n,r);
	int k=31-__builtin_clz(r-l+1);
	return min(mn[k][l],mn[k][r-(1<<k)+1]);
}

inline int getmx(int l,int r){
	l=max(1,l),r=min(n,r);
	int k=31-__builtin_clz(r-l+1);
	return max(mx[k][l],mx[k][r-(1<<k)+1]);
}

int main(){
	sf("%d%d%d",&n,&k,&m);
	for(int i=1;i<=n;++i)mn[0][i]=mx[0][i]=i;
	for(int i=0;i<m;++i){
		int a,b;sf("%d%d",&a,&b);
		if(a<b)mx[0][a]=max(mx[0][a],b);
		else mn[0][a]=min(mn[0][a],b);
	}
	for(int k=1;k<20;++k){
		for(int i=1;i+(1<<k)-1<=n;++i){
			mx[k][i]=max(mx[k-1][i],mx[k-1][i+(1<<(k-1))]);
			mn[k][i]=min(mn[k-1][i],mn[k-1][i+(1<<(k-1))]);
		}
	}
	sf("%d",&q);
	for(int i=0;i<q;++i){
		int s,t;sf("%d%d",&s,&t);
		int l=s,r=s,ans=0;
		while(t<l||r<t){
			int nr=max(r,getmx(l-k+1,r)),nl=min(l,getmn(l,r+k-1));
			if(nl==l&&nr==r){
				ans=-1;break;
			}
			l=nl,r=nr;
			++ans;
		}
		pf("%d\n",ans);
	}
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:30:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |  sf("%d%d%d",&n,&k,&m);
      |    ^
Main.cpp:33:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   int a,b;sf("%d%d",&a,&b);
      |             ^
Main.cpp:43:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  sf("%d",&q);
      |    ^
Main.cpp:45:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   int s,t;sf("%d%d",&s,&t);
      |             ^

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