oj.uz

답안 #581140

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
581140 2022-06-22T09:35:50 Z temporary_juggernaut Event Hopping (BOI22_events) C++14
25 / 100
 1500 ms 99276 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[100005];
pair<pair<int,int>,int>b[100005];
const int inf=1e9;
int pos[100005];
int fen[100005];
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 dp2[100005];
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(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++){
			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(dp[pos[x]][pos[y]]>=inf)puts("impossible");
			else printf("%d\n",dp[pos[x]][pos[y]]);
		}
		return 0;
	}else{
		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;
			}
			x=pos[x];
			y=pos[y];
			for(int i=1;i<=n;i++)dp2[i]=inf;
			dp2[x]=0;
			for(int j=1;j<=n+2;j++)fen[j]=inf;
			update(n-x+1,0);
			for(int j=x+1;j<=y;j++){
				dp2[j]=query(n-lf[j]+1)+1;
				update(n-j+1,dp2[j]);
			}
			if(dp2[y]>=inf)puts("impossible");
			else printf("%d\n",dp2[y]);
		}
		return 0;
	}
	return 1;
}

Compilation message

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

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 98252 KB Output is correct
2 Execution timed out 1566 ms 3784 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 98316 KB Output is correct
2 Correct 58 ms 98252 KB Output is correct
3 Correct 56 ms 98296 KB Output is correct
4 Correct 69 ms 98376 KB Output is correct
5 Correct 90 ms 98380 KB Output is correct
6 Correct 62 ms 98380 KB Output is correct
7 Correct 55 ms 98348 KB Output is correct
8 Correct 62 ms 98384 KB Output is correct
9 Correct 54 ms 98316 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 98316 KB Output is correct
2 Correct 58 ms 98252 KB Output is correct
3 Correct 56 ms 98296 KB Output is correct
4 Correct 69 ms 98376 KB Output is correct
5 Correct 90 ms 98380 KB Output is correct
6 Correct 62 ms 98380 KB Output is correct
7 Correct 55 ms 98348 KB Output is correct
8 Correct 62 ms 98384 KB Output is correct
9 Correct 54 ms 98316 KB Output is correct
10 Correct 64 ms 98280 KB Output is correct
11 Correct 62 ms 98228 KB Output is correct
12 Correct 67 ms 98364 KB Output is correct
13 Correct 53 ms 98400 KB Output is correct
14 Correct 57 ms 98280 KB Output is correct
15 Correct 55 ms 98364 KB Output is correct
16 Correct 57 ms 98380 KB Output is correct
17 Correct 68 ms 98348 KB Output is correct
18 Correct 63 ms 98296 KB Output is correct
19 Correct 311 ms 98892 KB Output is correct
20 Correct 348 ms 98992 KB Output is correct
21 Correct 329 ms 99268 KB Output is correct
22 Incorrect 443 ms 99276 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 98316 KB Output is correct
2 Correct 58 ms 98252 KB Output is correct
3 Correct 56 ms 98296 KB Output is correct
4 Correct 69 ms 98376 KB Output is correct
5 Correct 90 ms 98380 KB Output is correct
6 Correct 62 ms 98380 KB Output is correct
7 Correct 55 ms 98348 KB Output is correct
8 Correct 62 ms 98384 KB Output is correct
9 Correct 54 ms 98316 KB Output is correct
10 Correct 57 ms 98252 KB Output is correct
11 Correct 65 ms 98256 KB Output is correct
12 Correct 57 ms 98372 KB Output is correct
13 Correct 102 ms 98300 KB Output is correct
14 Correct 56 ms 98280 KB Output is correct
15 Correct 70 ms 98324 KB Output is correct
16 Correct 74 ms 98332 KB Output is correct
17 Correct 57 ms 98376 KB Output is correct
18 Correct 53 ms 98336 KB Output is correct
19 Correct 319 ms 3812 KB Output is correct
20 Correct 98 ms 3788 KB Output is correct
21 Correct 121 ms 3812 KB Output is correct
22 Correct 95 ms 3764 KB Output is correct
23 Correct 39 ms 3880 KB Output is correct
24 Correct 375 ms 3824 KB Output is correct
25 Correct 27 ms 3020 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1581 ms 3796 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 98252 KB Output is correct
2 Execution timed out 1566 ms 3784 KB Time limit exceeded
3 Halted 0 ms 0 KB -