oj.uz

Submission #580992

# Submission time Handle Problem Language Result Execution time Memory
580992 2022-06-22T07:48:36 Z temporary_juggernaut Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 98520 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 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=i+1;j<=n;j++){
				for(int k=1;k<j;k++)if(b[j].fr.fr<=b[k].fr.sc&&b[k].fr.sc<=b[j].fr.sc)umin(dp[i][j],dp[i][k]+1);
			}
		}
		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:32:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  scanf("%d%d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~
events.cpp:33:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |  for(int i=1;i<=n;i++)scanf("%d%d",&a[i].fr,&a[i].sc);
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:57:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |    scanf("%d%d",&x,&y);
      |    ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 98268 KB Output is correct
2 Runtime error 22 ms 1012 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 44 ms 98280 KB Output is correct
2 Correct 57 ms 98300 KB Output is correct
3 Correct 299 ms 98364 KB Output is correct
4 Correct 304 ms 98368 KB Output is correct
5 Correct 320 ms 98484 KB Output is correct
6 Correct 363 ms 98364 KB Output is correct
7 Correct 398 ms 98368 KB Output is correct
8 Correct 355 ms 98368 KB Output is correct
9 Correct 394 ms 98372 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 98280 KB Output is correct
2 Correct 57 ms 98300 KB Output is correct
3 Correct 299 ms 98364 KB Output is correct
4 Correct 304 ms 98368 KB Output is correct
5 Correct 320 ms 98484 KB Output is correct
6 Correct 363 ms 98364 KB Output is correct
7 Correct 398 ms 98368 KB Output is correct
8 Correct 355 ms 98368 KB Output is correct
9 Correct 394 ms 98372 KB Output is correct
10 Correct 43 ms 98252 KB Output is correct
11 Correct 45 ms 98264 KB Output is correct
12 Correct 304 ms 98372 KB Output is correct
13 Correct 362 ms 98368 KB Output is correct
14 Correct 293 ms 98384 KB Output is correct
15 Correct 360 ms 98372 KB Output is correct
16 Correct 349 ms 98364 KB Output is correct
17 Correct 352 ms 98344 KB Output is correct
18 Correct 352 ms 98252 KB Output is correct
19 Execution timed out 1582 ms 98520 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 98280 KB Output is correct
2 Correct 57 ms 98300 KB Output is correct
3 Correct 299 ms 98364 KB Output is correct
4 Correct 304 ms 98368 KB Output is correct
5 Correct 320 ms 98484 KB Output is correct
6 Correct 363 ms 98364 KB Output is correct
7 Correct 398 ms 98368 KB Output is correct
8 Correct 355 ms 98368 KB Output is correct
9 Correct 394 ms 98372 KB Output is correct
10 Correct 62 ms 98276 KB Output is correct
11 Correct 51 ms 98228 KB Output is correct
12 Correct 317 ms 98372 KB Output is correct
13 Correct 319 ms 98368 KB Output is correct
14 Correct 336 ms 98388 KB Output is correct
15 Correct 351 ms 98368 KB Output is correct
16 Correct 421 ms 98368 KB Output is correct
17 Correct 368 ms 98368 KB Output is correct
18 Correct 404 ms 98368 KB Output is correct
19 Runtime error 21 ms 980 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 22 ms 1048 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 41 ms 98268 KB Output is correct
2 Runtime error 22 ms 1012 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -