oj.uz

Submission #678763

# Submission time Handle Problem Language Result Execution time Memory
678763 2023-01-06T13:43:53 Z jamezzz Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 266648 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define psf push_front
#define ppb pop_back
#define ppf pop_front
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(),x.end()
#define lb(x,v) (lower_bound(all(x),v)-x.begin())
#define ub(x,v) (upper_bound(all(x),v)-x.begin())
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> iii;
typedef tuple<int,int,int,int> iiii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
mt19937 rng(time(0));

#define mod 1000000007

inline int add(int a,int b){
	int r=a+b;
	while(r>=mod)r-=mod;
	while(r<0)r+=mod;
	return r;
}

inline int mult(int a,int b){
	return (int)(((ll)(a*b))%mod);
}

inline int rd(){
	int x=0;
	char ch=getchar_unlocked();
	while(!(ch&16))ch=getchar();//keep reading while current character is whitespace
    while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered
		x=(x<<3)+(x<<1)+(ch&15);
		ch=getchar_unlocked();
	}
	return x;
}

#define maxn 100005

int n,q,s[maxn],e[maxn];
set<ii> nx[maxn];

int main(){
	sf("%d%d",&n,&q);
	for(int i=0;i<n;++i){
		sf("%d%d",&s[i],&e[i]);
	}
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j){
			if(i==j)continue;
			if(s[j]<=e[i]&&e[i]<=e[j]){
				nx[i].insert({e[j],j});
			}
		}
	}
	for(int i=0;i<q;++i){
		int l,r;sf("%d%d",&l,&r);
		--l,--r;
		int ans=0;
		while(l!=r){
			if(nx[l].count({e[r],r})){
				++ans;break;
			}
			if(nx[l].empty()||e[r]<(*nx[l].begin()).fi){
				ans=-1;break;
			}
			auto it=--nx[l].upper_bound({e[r],INF});
			if((*it).fi==e[l]){
				ans=-1;break;
			}
			l=(*it).se;++ans;
		}
		if(ans!=-1)pf("%d\n",ans);
		else pf("impossible\n");
	}
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:68:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |  sf("%d%d",&n,&q);
      |    ^
events.cpp:70:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   sf("%d%d",&s[i],&e[i]);
      |     ^
events.cpp:81:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |   int l,r;sf("%d%d",&l,&r);
      |             ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Execution timed out 1588 ms 6064 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 7 ms 5076 KB Output is correct
4 Correct 7 ms 5076 KB Output is correct
5 Correct 6 ms 5076 KB Output is correct
6 Correct 28 ms 12024 KB Output is correct
7 Correct 55 ms 20388 KB Output is correct
8 Correct 81 ms 28436 KB Output is correct
9 Correct 111 ms 51888 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 7 ms 5076 KB Output is correct
4 Correct 7 ms 5076 KB Output is correct
5 Correct 6 ms 5076 KB Output is correct
6 Correct 28 ms 12024 KB Output is correct
7 Correct 55 ms 20388 KB Output is correct
8 Correct 81 ms 28436 KB Output is correct
9 Correct 111 ms 51888 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 5016 KB Output is correct
12 Correct 7 ms 5076 KB Output is correct
13 Correct 6 ms 5040 KB Output is correct
14 Correct 6 ms 5020 KB Output is correct
15 Correct 29 ms 11988 KB Output is correct
16 Correct 58 ms 20376 KB Output is correct
17 Correct 85 ms 28376 KB Output is correct
18 Correct 113 ms 51916 KB Output is correct
19 Execution timed out 1587 ms 266648 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 7 ms 5076 KB Output is correct
4 Correct 7 ms 5076 KB Output is correct
5 Correct 6 ms 5076 KB Output is correct
6 Correct 28 ms 12024 KB Output is correct
7 Correct 55 ms 20388 KB Output is correct
8 Correct 81 ms 28436 KB Output is correct
9 Correct 111 ms 51888 KB Output is correct
10 Correct 4 ms 4948 KB Output is correct
11 Correct 3 ms 5016 KB Output is correct
12 Correct 7 ms 5092 KB Output is correct
13 Correct 6 ms 5036 KB Output is correct
14 Correct 6 ms 5076 KB Output is correct
15 Correct 27 ms 11924 KB Output is correct
16 Correct 56 ms 20380 KB Output is correct
17 Correct 86 ms 28492 KB Output is correct
18 Correct 112 ms 51924 KB Output is correct
19 Execution timed out 1564 ms 8100 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Execution timed out 1588 ms 6064 KB Time limit exceeded
3 Halted 0 ms 0 KB -