oj.uz

Submission #581001

# Submission time Handle Problem Language Result Execution time Memory
581001 2022-06-22T08:06:51 Z temporary_juggernaut Event Hopping (BOI22_events) C++14
40 / 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(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;
	}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:93:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |    scanf("%d%d",&x,&y);
      |    ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 98256 KB Output is correct
2 Execution timed out 1588 ms 3792 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 98324 KB Output is correct
2 Correct 43 ms 98244 KB Output is correct
3 Correct 50 ms 98320 KB Output is correct
4 Correct 54 ms 98380 KB Output is correct
5 Correct 49 ms 98368 KB Output is correct
6 Correct 55 ms 98368 KB Output is correct
7 Correct 56 ms 98348 KB Output is correct
8 Correct 51 ms 98308 KB Output is correct
9 Correct 77 ms 98380 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 98324 KB Output is correct
2 Correct 43 ms 98244 KB Output is correct
3 Correct 50 ms 98320 KB Output is correct
4 Correct 54 ms 98380 KB Output is correct
5 Correct 49 ms 98368 KB Output is correct
6 Correct 55 ms 98368 KB Output is correct
7 Correct 56 ms 98348 KB Output is correct
8 Correct 51 ms 98308 KB Output is correct
9 Correct 77 ms 98380 KB Output is correct
10 Correct 79 ms 98340 KB Output is correct
11 Correct 62 ms 98340 KB Output is correct
12 Correct 61 ms 98280 KB Output is correct
13 Correct 53 ms 98388 KB Output is correct
14 Correct 49 ms 98312 KB Output is correct
15 Correct 54 ms 98376 KB Output is correct
16 Correct 57 ms 98272 KB Output is correct
17 Correct 51 ms 98296 KB Output is correct
18 Correct 53 ms 98376 KB Output is correct
19 Correct 302 ms 98920 KB Output is correct
20 Correct 313 ms 98952 KB Output is correct
21 Correct 319 ms 99276 KB Output is correct
22 Correct 422 ms 99272 KB Output is correct
23 Correct 417 ms 99144 KB Output is correct
24 Correct 311 ms 99148 KB Output is correct
25 Correct 339 ms 98760 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 98324 KB Output is correct
2 Correct 43 ms 98244 KB Output is correct
3 Correct 50 ms 98320 KB Output is correct
4 Correct 54 ms 98380 KB Output is correct
5 Correct 49 ms 98368 KB Output is correct
6 Correct 55 ms 98368 KB Output is correct
7 Correct 56 ms 98348 KB Output is correct
8 Correct 51 ms 98308 KB Output is correct
9 Correct 77 ms 98380 KB Output is correct
10 Correct 52 ms 98276 KB Output is correct
11 Correct 61 ms 98236 KB Output is correct
12 Correct 63 ms 98296 KB Output is correct
13 Correct 62 ms 98404 KB Output is correct
14 Correct 50 ms 98324 KB Output is correct
15 Correct 77 ms 98360 KB Output is correct
16 Correct 54 ms 98368 KB Output is correct
17 Correct 52 ms 98324 KB Output is correct
18 Correct 65 ms 98332 KB Output is correct
19 Correct 322 ms 3748 KB Output is correct
20 Correct 90 ms 3784 KB Output is correct
21 Correct 100 ms 3716 KB Output is correct
22 Correct 94 ms 3784 KB Output is correct
23 Correct 39 ms 3796 KB Output is correct
24 Correct 341 ms 4112 KB Output is correct
25 Correct 29 ms 3020 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1582 ms 3792 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 98256 KB Output is correct
2 Execution timed out 1588 ms 3792 KB Time limit exceeded
3 Halted 0 ms 0 KB -