oj.uz

Submission #580997

# Submission time Handle Problem Language Result Execution time Memory
580997 2022-06-22T08:01:21 Z temporary_juggernaut Event Hopping (BOI22_events) C++14
25 / 100
 463 ms 99252 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];
int vis[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 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;
	}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;
			}
			puts("impossible");
		}
	}
	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 44 ms 98308 KB Output is correct
2 Runtime error 48 ms 2168 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 98300 KB Output is correct
2 Correct 46 ms 98260 KB Output is correct
3 Correct 53 ms 98380 KB Output is correct
4 Correct 57 ms 98324 KB Output is correct
5 Correct 51 ms 98268 KB Output is correct
6 Correct 57 ms 98376 KB Output is correct
7 Correct 62 ms 98340 KB Output is correct
8 Correct 55 ms 98380 KB Output is correct
9 Correct 57 ms 98368 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 98300 KB Output is correct
2 Correct 46 ms 98260 KB Output is correct
3 Correct 53 ms 98380 KB Output is correct
4 Correct 57 ms 98324 KB Output is correct
5 Correct 51 ms 98268 KB Output is correct
6 Correct 57 ms 98376 KB Output is correct
7 Correct 62 ms 98340 KB Output is correct
8 Correct 55 ms 98380 KB Output is correct
9 Correct 57 ms 98368 KB Output is correct
10 Correct 45 ms 98280 KB Output is correct
11 Correct 44 ms 98236 KB Output is correct
12 Correct 53 ms 98356 KB Output is correct
13 Correct 54 ms 98344 KB Output is correct
14 Correct 52 ms 98364 KB Output is correct
15 Correct 58 ms 98508 KB Output is correct
16 Correct 58 ms 98384 KB Output is correct
17 Correct 54 ms 98436 KB Output is correct
18 Correct 53 ms 98380 KB Output is correct
19 Correct 349 ms 98940 KB Output is correct
20 Correct 354 ms 98872 KB Output is correct
21 Correct 346 ms 99200 KB Output is correct
22 Correct 463 ms 99252 KB Output is correct
23 Correct 428 ms 99124 KB Output is correct
24 Correct 290 ms 99020 KB Output is correct
25 Correct 419 ms 98696 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 98300 KB Output is correct
2 Correct 46 ms 98260 KB Output is correct
3 Correct 53 ms 98380 KB Output is correct
4 Correct 57 ms 98324 KB Output is correct
5 Correct 51 ms 98268 KB Output is correct
6 Correct 57 ms 98376 KB Output is correct
7 Correct 62 ms 98340 KB Output is correct
8 Correct 55 ms 98380 KB Output is correct
9 Correct 57 ms 98368 KB Output is correct
10 Correct 47 ms 98380 KB Output is correct
11 Correct 44 ms 98340 KB Output is correct
12 Correct 59 ms 98312 KB Output is correct
13 Correct 57 ms 98372 KB Output is correct
14 Correct 62 ms 98344 KB Output is correct
15 Correct 55 ms 98332 KB Output is correct
16 Correct 60 ms 98292 KB Output is correct
17 Correct 54 ms 98380 KB Output is correct
18 Correct 52 ms 98320 KB Output is correct
19 Runtime error 26 ms 968 KB Execution failed because the return code was nonzero
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 2132 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 98308 KB Output is correct
2 Runtime error 48 ms 2168 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -