oj.uz

Submission #580995

# Submission time Handle Problem Language Result Execution time Memory
580995 2022-06-22T07:58:16 Z temporary_juggernaut Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 98500 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];
void update(int pos,int val){
	fen[pos]=val;
	/*while(pos<=n+2){
		umin(fen[pos],val);
		pos+=(pos&-pos);
	}*/
}
int query(int pos){
	int ans=inf;
	while(pos){
		umax(ans,fen[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;
	}
	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);
      |    ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 98252 KB Output is correct
2 Runtime error 19 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 53 ms 98324 KB Output is correct
2 Correct 46 ms 98244 KB Output is correct
3 Correct 178 ms 98380 KB Output is correct
4 Correct 174 ms 98436 KB Output is correct
5 Correct 164 ms 98336 KB Output is correct
6 Correct 253 ms 98492 KB Output is correct
7 Correct 321 ms 98296 KB Output is correct
8 Correct 394 ms 98380 KB Output is correct
9 Correct 410 ms 98384 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 98324 KB Output is correct
2 Correct 46 ms 98244 KB Output is correct
3 Correct 178 ms 98380 KB Output is correct
4 Correct 174 ms 98436 KB Output is correct
5 Correct 164 ms 98336 KB Output is correct
6 Correct 253 ms 98492 KB Output is correct
7 Correct 321 ms 98296 KB Output is correct
8 Correct 394 ms 98380 KB Output is correct
9 Correct 410 ms 98384 KB Output is correct
10 Correct 49 ms 98328 KB Output is correct
11 Correct 45 ms 98360 KB Output is correct
12 Correct 194 ms 98384 KB Output is correct
13 Correct 170 ms 98376 KB Output is correct
14 Correct 166 ms 98376 KB Output is correct
15 Correct 261 ms 98380 KB Output is correct
16 Correct 353 ms 98444 KB Output is correct
17 Correct 419 ms 98380 KB Output is correct
18 Correct 403 ms 98384 KB Output is correct
19 Execution timed out 1598 ms 98416 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 98324 KB Output is correct
2 Correct 46 ms 98244 KB Output is correct
3 Correct 178 ms 98380 KB Output is correct
4 Correct 174 ms 98436 KB Output is correct
5 Correct 164 ms 98336 KB Output is correct
6 Correct 253 ms 98492 KB Output is correct
7 Correct 321 ms 98296 KB Output is correct
8 Correct 394 ms 98380 KB Output is correct
9 Correct 410 ms 98384 KB Output is correct
10 Correct 42 ms 98380 KB Output is correct
11 Correct 43 ms 98304 KB Output is correct
12 Correct 181 ms 98380 KB Output is correct
13 Correct 172 ms 98396 KB Output is correct
14 Correct 170 ms 98324 KB Output is correct
15 Correct 255 ms 98376 KB Output is correct
16 Correct 328 ms 98500 KB Output is correct
17 Correct 402 ms 98372 KB Output is correct
18 Correct 483 ms 98376 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 21 ms 1040 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 45 ms 98252 KB Output is correct
2 Runtime error 19 ms 980 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -