oj.uz

Submission #581000

# Submission time Handle Problem Language Result Execution time Memory
581000 2022-06-22T08:06:09 Z temporary_juggernaut Event Hopping (BOI22_events) C++14
25 / 100
 1500 ms 99276 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[100005];
pair<pair<int,int>,int>b[100005];
const int inf=1e9;
int pos[100005];
int fen[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 dp2[100005];
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)scanf("%d%d",&a[i].fr,&a[i].sc);
	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;
	}
	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++){
			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;
			}
			for(int i=1;i<=n;i++)dp2[i]=inf;
			dp2[x]=0;
			for(int j=1;j<=n+2;j++)fen[j]=inf;
			update(n-x+1,0);
			for(int j=x+1;j<=y;j++){
				dp2[j]=query(n-lf[j]+1)+1;
				update(n-j+1,dp2[j]);
			}
			if(dp2[y]>=inf)puts("impossible");
			else printf("%d\n",dp2[y]);
		}
		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 42 ms 98312 KB Output is correct
2 Execution timed out 1585 ms 3916 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 98252 KB Output is correct
2 Correct 45 ms 98332 KB Output is correct
3 Correct 59 ms 98312 KB Output is correct
4 Correct 53 ms 98380 KB Output is correct
5 Correct 51 ms 98352 KB Output is correct
6 Correct 53 ms 98380 KB Output is correct
7 Correct 56 ms 98260 KB Output is correct
8 Correct 58 ms 98324 KB Output is correct
9 Correct 56 ms 98384 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 98252 KB Output is correct
2 Correct 45 ms 98332 KB Output is correct
3 Correct 59 ms 98312 KB Output is correct
4 Correct 53 ms 98380 KB Output is correct
5 Correct 51 ms 98352 KB Output is correct
6 Correct 53 ms 98380 KB Output is correct
7 Correct 56 ms 98260 KB Output is correct
8 Correct 58 ms 98324 KB Output is correct
9 Correct 56 ms 98384 KB Output is correct
10 Correct 44 ms 98280 KB Output is correct
11 Correct 52 ms 98260 KB Output is correct
12 Correct 53 ms 98380 KB Output is correct
13 Correct 60 ms 98284 KB Output is correct
14 Correct 52 ms 98300 KB Output is correct
15 Correct 55 ms 98264 KB Output is correct
16 Correct 57 ms 98364 KB Output is correct
17 Correct 53 ms 98380 KB Output is correct
18 Correct 55 ms 98380 KB Output is correct
19 Correct 325 ms 98948 KB Output is correct
20 Correct 355 ms 98888 KB Output is correct
21 Correct 338 ms 99276 KB Output is correct
22 Correct 476 ms 99268 KB Output is correct
23 Correct 442 ms 99144 KB Output is correct
24 Correct 344 ms 99232 KB Output is correct
25 Correct 373 ms 98696 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 98252 KB Output is correct
2 Correct 45 ms 98332 KB Output is correct
3 Correct 59 ms 98312 KB Output is correct
4 Correct 53 ms 98380 KB Output is correct
5 Correct 51 ms 98352 KB Output is correct
6 Correct 53 ms 98380 KB Output is correct
7 Correct 56 ms 98260 KB Output is correct
8 Correct 58 ms 98324 KB Output is correct
9 Correct 56 ms 98384 KB Output is correct
10 Correct 46 ms 98252 KB Output is correct
11 Correct 46 ms 98236 KB Output is correct
12 Correct 54 ms 98452 KB Output is correct
13 Correct 51 ms 98296 KB Output is correct
14 Correct 59 ms 98296 KB Output is correct
15 Correct 56 ms 98380 KB Output is correct
16 Correct 56 ms 98380 KB Output is correct
17 Correct 56 ms 98360 KB Output is correct
18 Correct 52 ms 98272 KB Output is correct
19 Incorrect 87 ms 3796 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1569 ms 3816 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 98312 KB Output is correct
2 Execution timed out 1585 ms 3916 KB Time limit exceeded
3 Halted 0 ms 0 KB -