제출 #581035

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
581035		juggernaut	Event Hopping (BOI22_events)	C++14	0 / 100	130 ms	20932 KiB

events

#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
#define USING_ORDERED_SET 0
#if USING_ORDERED_SET
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#endif
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
    #define printl(args...) printf(args)
#else
    #define printl(args...) 0
#endif
int n,q;
pair<int,int>a[100005];
bool cmp(pair<pair<int,int>,int>l,pair<pair<int,int>,int>r){
	if(l.fr.sc==r.fr.sc)return l.fr.fr<r.fr.fr;
	return l.fr.sc<r.fr.sc;
}
int lf[100005];
pair<pair<int,int>,int>b[100005];
const int inf=1e9;
int pos[100005];
int up[100005][20];
vector<int>g[100005];
int depth[100005];
void dfs(int v,int p){
	up[v][0]=p;
	depth[v]=depth[p]+1;
	for(int i=1;i<19;i++)up[v][i]=up[up[v][i-1]][i-1];
	for(int to:g[v])dfs(to,v);
}
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)scanf("%d%d",&a[i].fr,&a[i].sc);
	for(int i=1;i<=n;i++)b[i]=make_pair(a[i],i);
	sort(b+1,b+1+n,cmp);
	for(int i=1;i<=n;i++)pos[b[i].sc]=i;
	for(int i=1;i<=n;i++){
		int l=1,r=i;
		while(l<r){
			int mid=(l+r)>>1;
			if(b[i].fr.fr<=b[mid].fr.sc)r=mid;
			else l=mid+1;
		}
		lf[i]=l;
		if(lf[i]==l){
			lf[i]=0;
			if(i<n&&b[i+1].fr.fr<=b[i].fr.sc&&b[i].fr.sc<=b[i+1].fr.sc)lf[i]=i+1;
		}
		g[pos[lf[i]]].push_back(pos[i]);
	}
	dfs(0,0);
	while(q--){
		int x,y;
		scanf("%d%d",&x,&y);
		if(x==y){
			puts("0");
			continue;
		}
		if(a[y].fr<=a[x].sc&&a[x].sc<=a[y].sc){
			puts("1");
			continue;
		}
		swap(x,y);
		if(depth[x]<depth[y])puts("impossible");
		else{
			int dist=depth[x]-depth[y];
			for(int i=19;i>=0;i--)if(dist>>i&1)x=up[x][i];
			if(x==y)printf("%d\n",dist);
			else puts("impossible");
		}
	}
}

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

events.cpp: In function 'int main()':
events.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  scanf("%d%d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~
events.cpp:41:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  for(int i=1;i<=n;i++)scanf("%d%d",&a[i].fr,&a[i].sc);
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   scanf("%d%d",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30