oj.uz

Submission #580998

# Submission time Handle Problem Language Result Execution time Memory
580998 2022-06-22T08:01:49 Z temporary_juggernaut Event Hopping (BOI22_events) C++14
25 / 100
 461 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 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 52 ms 98380 KB Output is correct
2 Incorrect 46 ms 2076 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 98252 KB Output is correct
2 Correct 55 ms 98244 KB Output is correct
3 Correct 60 ms 98340 KB Output is correct
4 Correct 61 ms 98332 KB Output is correct
5 Correct 59 ms 98308 KB Output is correct
6 Correct 64 ms 98336 KB Output is correct
7 Correct 78 ms 98324 KB Output is correct
8 Correct 62 ms 98384 KB Output is correct
9 Correct 64 ms 98376 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 98252 KB Output is correct
2 Correct 55 ms 98244 KB Output is correct
3 Correct 60 ms 98340 KB Output is correct
4 Correct 61 ms 98332 KB Output is correct
5 Correct 59 ms 98308 KB Output is correct
6 Correct 64 ms 98336 KB Output is correct
7 Correct 78 ms 98324 KB Output is correct
8 Correct 62 ms 98384 KB Output is correct
9 Correct 64 ms 98376 KB Output is correct
10 Correct 56 ms 98320 KB Output is correct
11 Correct 54 ms 98280 KB Output is correct
12 Correct 63 ms 98304 KB Output is correct
13 Correct 60 ms 98376 KB Output is correct
14 Correct 62 ms 98340 KB Output is correct
15 Correct 63 ms 98380 KB Output is correct
16 Correct 63 ms 98276 KB Output is correct
17 Correct 60 ms 98376 KB Output is correct
18 Correct 65 ms 98304 KB Output is correct
19 Correct 322 ms 98956 KB Output is correct
20 Correct 329 ms 98900 KB Output is correct
21 Correct 326 ms 99212 KB Output is correct
22 Correct 461 ms 99252 KB Output is correct
23 Correct 444 ms 99124 KB Output is correct
24 Correct 303 ms 99148 KB Output is correct
25 Correct 349 ms 98788 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 98252 KB Output is correct
2 Correct 55 ms 98244 KB Output is correct
3 Correct 60 ms 98340 KB Output is correct
4 Correct 61 ms 98332 KB Output is correct
5 Correct 59 ms 98308 KB Output is correct
6 Correct 64 ms 98336 KB Output is correct
7 Correct 78 ms 98324 KB Output is correct
8 Correct 62 ms 98384 KB Output is correct
9 Correct 64 ms 98376 KB Output is correct
10 Correct 52 ms 98324 KB Output is correct
11 Correct 50 ms 98360 KB Output is correct
12 Correct 59 ms 98364 KB Output is correct
13 Correct 62 ms 98272 KB Output is correct
14 Correct 59 ms 98328 KB Output is correct
15 Correct 63 ms 98296 KB Output is correct
16 Correct 63 ms 98336 KB Output is correct
17 Correct 61 ms 98324 KB Output is correct
18 Correct 62 ms 98384 KB Output is correct
19 Incorrect 23 ms 980 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 2076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 98380 KB Output is correct
2 Incorrect 46 ms 2076 KB Output isn't correct
3 Halted 0 ms 0 KB -