제출 #638736

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
638736		jamezzz	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	1648 ms	203628 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

struct node{
	int s,e,m;pair<int,int> v;
	node *l,*r;
	node(int _s,int _e){
		s=_s;e=_e;m=(s+e)>>1;v={0,0};
		if(s!=e)l=new node(s,m),r=new node(m+1,e);
	}
	void up(int x,ii nv){
		if(s==x&&e==x){v=nv;return;}
		if(x<=m)l->up(x,nv);
		else r->up(x,nv);
		v={min(l->v.fi,r->v.fi),max(l->v.se,r->v.se)};
	}
	ii qry(int x,int y){
		if(s==x&&e==y)return v;
		if(y<=m)return l->qry(x,y);
		if(x>m)return r->qry(x,y);
		ii pl=qry(x,m),pr=qry(m+1,y);
		return {min(pl.fi,pr.fi),max(pl.se,pr.se)};
	}
}*rt[20];

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);
		mx[0][a]=max(mx[0][a],b);
		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))]);
		}
	}
	rt[0]=new node(1,n);
	//pf("0: ");
	for(int i=1;i<=n;++i){
		int l=min(i,getmn(i,i+k-1)),r=max(i,getmx(i-k+1,i));
		rt[0]->up(i,{l,r});
		//pf("(%d: %d %d) ",i,l,r);
	}
	//pf("\n");
	for(int k=1;k<20;++k){
		rt[k]=new node(1,n);
		//pf("%d: ",k);
		for(int i=1;i<=n;++i){
			ii pr=rt[k-1]->qry(i,i);
			rt[k]->up(i,rt[k-1]->qry(pr.fi,pr.se));
			//pf("(%d: %d %d) ",i,rt[k]->qry(i,i).fi,rt[k]->qry(i,i).se);
		}
		//pf("\n");
	}
	sf("%d",&q);
	for(int i=0;i<q;++i){
		int s,t;sf("%d%d",&s,&t);
		ii pr=rt[19]->qry(s,s);
		if(t<pr.fi||pr.se<t){
			pf("-1\n");
			continue;
		}
		int l=s,r=s,ans=0;
		for(int k=19;k>=0;--k){
			ii pr=rt[k]->qry(l,r);
			if(t<pr.fi||pr.se<t){
				ans+=(1<<k);
				tie(l,r)=pr;
			}
		}
		pf("%d\n",ans+1);
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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

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