oj.uz

Submission #580993

# Submission time Handle Problem Language Result Execution time Memory
580993 2022-06-22T07:49:13 Z temporary_juggernaut Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 98420 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=lf[j];k<j;k++)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 46 ms 98248 KB Output is correct
2 Runtime error 23 ms 980 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 49 ms 98252 KB Output is correct
2 Correct 48 ms 98252 KB Output is correct
3 Correct 52 ms 98252 KB Output is correct
4 Correct 49 ms 98252 KB Output is correct
5 Correct 53 ms 98332 KB Output is correct
6 Correct 135 ms 98256 KB Output is correct
7 Correct 222 ms 98368 KB Output is correct
8 Correct 352 ms 98368 KB Output is correct
9 Correct 293 ms 98364 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 98252 KB Output is correct
2 Correct 48 ms 98252 KB Output is correct
3 Correct 52 ms 98252 KB Output is correct
4 Correct 49 ms 98252 KB Output is correct
5 Correct 53 ms 98332 KB Output is correct
6 Correct 135 ms 98256 KB Output is correct
7 Correct 222 ms 98368 KB Output is correct
8 Correct 352 ms 98368 KB Output is correct
9 Correct 293 ms 98364 KB Output is correct
10 Correct 47 ms 98272 KB Output is correct
11 Correct 61 ms 98240 KB Output is correct
12 Correct 62 ms 98324 KB Output is correct
13 Correct 48 ms 98356 KB Output is correct
14 Correct 48 ms 98292 KB Output is correct
15 Correct 148 ms 98372 KB Output is correct
16 Correct 242 ms 98364 KB Output is correct
17 Correct 317 ms 98340 KB Output is correct
18 Correct 319 ms 98420 KB Output is correct
19 Execution timed out 1582 ms 98364 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 98252 KB Output is correct
2 Correct 48 ms 98252 KB Output is correct
3 Correct 52 ms 98252 KB Output is correct
4 Correct 49 ms 98252 KB Output is correct
5 Correct 53 ms 98332 KB Output is correct
6 Correct 135 ms 98256 KB Output is correct
7 Correct 222 ms 98368 KB Output is correct
8 Correct 352 ms 98368 KB Output is correct
9 Correct 293 ms 98364 KB Output is correct
10 Correct 53 ms 98316 KB Output is correct
11 Correct 47 ms 98272 KB Output is correct
12 Correct 49 ms 98300 KB Output is correct
13 Correct 54 ms 98372 KB Output is correct
14 Correct 52 ms 98336 KB Output is correct
15 Correct 144 ms 98284 KB Output is correct
16 Correct 271 ms 98368 KB Output is correct
17 Correct 305 ms 98368 KB Output is correct
18 Correct 323 ms 98364 KB Output is correct
19 Runtime error 24 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 988 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 46 ms 98248 KB Output is correct
2 Runtime error 23 ms 980 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -