oj.uz

답안 #580996

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
580996 2022-06-22T07:59:15 Z temporary_juggernaut Event Hopping (BOI22_events) C++14
25 / 100
 466 ms 99316 KB 
#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 dp[5005][5005];
int lf[5005];
pair<pair<int,int>,int>b[5005];
const int inf=1e9;
int pos[5005];
int fen[5005];
void update(int pos,int val){
	while(pos<=n+2){
		umin(fen[pos],val);
		pos+=(pos&-pos);
	}
}
int query(int pos){
	int ans=inf;
	while(pos){
		umin(ans,fen[pos]);
		pos-=(pos&-pos);
	}
	return ans;
}
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)scanf("%d%d",&a[i].fr,&a[i].sc);
	if(n<=5000){
		for(int i=0;i<5005;i++)
		for(int j=0;j<5005;j++)dp[i][j]=inf;
		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;
		}
		for(int i=1;i<=n;i++){
			dp[i][i]=0;
			for(int j=1;j<=n+2;j++)fen[j]=inf;
			update(n-i+1,0);
			for(int j=i+1;j<=n;j++){
				dp[i][j]=query(n-lf[j]+1)+1;
				//for(int k=lf[j];k<=n;k++)umin(dp[i][j],dp[i][k]+1);
				update(n-j+1,dp[i][j]);
			}
		}
		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;
			}
			if(dp[pos[x]][pos[y]]>=inf)puts("impossible");
			else printf("%d\n",dp[pos[x]][pos[y]]);
		}
		return 0;
	}
	return 1;
}

Compilation message

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

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 98304 KB Output is correct
2 Runtime error 23 ms 972 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 98268 KB Output is correct
2 Correct 44 ms 98248 KB Output is correct
3 Correct 64 ms 98380 KB Output is correct
4 Correct 50 ms 98344 KB Output is correct
5 Correct 55 ms 98328 KB Output is correct
6 Correct 60 ms 98376 KB Output is correct
7 Correct 68 ms 98384 KB Output is correct
8 Correct 64 ms 98312 KB Output is correct
9 Correct 56 ms 98276 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 98268 KB Output is correct
2 Correct 44 ms 98248 KB Output is correct
3 Correct 64 ms 98380 KB Output is correct
4 Correct 50 ms 98344 KB Output is correct
5 Correct 55 ms 98328 KB Output is correct
6 Correct 60 ms 98376 KB Output is correct
7 Correct 68 ms 98384 KB Output is correct
8 Correct 64 ms 98312 KB Output is correct
9 Correct 56 ms 98276 KB Output is correct
10 Correct 44 ms 98296 KB Output is correct
11 Correct 45 ms 98252 KB Output is correct
12 Correct 57 ms 98360 KB Output is correct
13 Correct 66 ms 98348 KB Output is correct
14 Correct 63 ms 98396 KB Output is correct
15 Correct 62 ms 98296 KB Output is correct
16 Correct 55 ms 98272 KB Output is correct
17 Correct 54 ms 98380 KB Output is correct
18 Correct 53 ms 98276 KB Output is correct
19 Correct 354 ms 98868 KB Output is correct
20 Correct 401 ms 98900 KB Output is correct
21 Correct 385 ms 99252 KB Output is correct
22 Correct 449 ms 99316 KB Output is correct
23 Correct 466 ms 99132 KB Output is correct
24 Correct 337 ms 99264 KB Output is correct
25 Correct 385 ms 98784 KB Output is correct

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 98268 KB Output is correct
2 Correct 44 ms 98248 KB Output is correct
3 Correct 64 ms 98380 KB Output is correct
4 Correct 50 ms 98344 KB Output is correct
5 Correct 55 ms 98328 KB Output is correct
6 Correct 60 ms 98376 KB Output is correct
7 Correct 68 ms 98384 KB Output is correct
8 Correct 64 ms 98312 KB Output is correct
9 Correct 56 ms 98276 KB Output is correct
10 Correct 55 ms 98380 KB Output is correct
11 Correct 53 ms 98308 KB Output is correct
12 Correct 54 ms 98312 KB Output is correct
13 Correct 63 ms 98360 KB Output is correct
14 Correct 57 ms 98380 KB Output is correct
15 Correct 56 ms 98304 KB Output is correct
16 Correct 61 ms 98308 KB Output is correct
17 Correct 68 ms 98380 KB Output is correct
18 Correct 58 ms 98380 KB Output is correct
19 Runtime error 20 ms 1076 KB Execution failed because the return code was nonzero
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 27 ms 980 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 98304 KB Output is correct
2 Runtime error 23 ms 972 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -