oj.uz

Submission #580985

# Submission time Handle Problem Language Result Execution time Memory
580985 2022-06-22T07:38:06 Z temporary_juggernaut Event Hopping (BOI22_events) C++14
0 / 100
 155 ms 98372 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){
	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:31:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  scanf("%d%d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~
events.cpp:32:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  for(int i=1;i<=n;i++)scanf("%d%d",&a[i].fr,&a[i].sc);
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:56:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |    scanf("%d%d",&x,&y);
      |    ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 98344 KB Output is correct
2 Runtime error 29 ms 980 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 98240 KB Output is correct
2 Correct 49 ms 98252 KB Output is correct
3 Correct 63 ms 98356 KB Output is correct
4 Correct 48 ms 98356 KB Output is correct
5 Correct 60 ms 98308 KB Output is correct
6 Incorrect 155 ms 98372 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 98240 KB Output is correct
2 Correct 49 ms 98252 KB Output is correct
3 Correct 63 ms 98356 KB Output is correct
4 Correct 48 ms 98356 KB Output is correct
5 Correct 60 ms 98308 KB Output is correct
6 Incorrect 155 ms 98372 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 98240 KB Output is correct
2 Correct 49 ms 98252 KB Output is correct
3 Correct 63 ms 98356 KB Output is correct
4 Correct 48 ms 98356 KB Output is correct
5 Correct 60 ms 98308 KB Output is correct
6 Incorrect 155 ms 98372 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 1028 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 43 ms 98344 KB Output is correct
2 Runtime error 29 ms 980 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -