oj.uz

Submission #849505

# Submission time Handle Problem Language Result Execution time Memory
849505 2023-09-14T18:58:10 Z vjudge1 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 15952 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define endl '\n'
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
const int mod = 1e9 + 7;
const int N = 1e5 + 15;
const ll inf = 1e18;
int n,q;
int dis[N];
struct segtree{
	static const int off = (1<<18);
	int t[off*2];
	int unit;
	void init(){
		memset(t, 0x3f, sizeof(t));
		unit = t[0];
	}
	void update(int i,int u){
		i+=off;
		if (u >= t[i]) return;
		t[i] = u;
		while (i/=2){
			t[i] = min(t[i*2],t[i*2+1]);
		}
	}
	int get(int l, int r, int idx=1, int lo=0, int hi=off){
		if (lo>=r||hi<=l) return unit;
		if (lo>=l&&hi<=r) return t[idx];
		int mi = (lo+hi)/2;
		return min(get(l,r,idx*2,lo,mi),get(l,r,idx*2+1,mi,hi));
	}
} seg;
vector<array<int, 3>> a;
bool cmp(array<int, 3> A, array<int, 3> B){
	if (A[1]!=B[1]) return A[1] < B[1];
	return A[0] < B[0];
}
pii b[N];
int solve(int root, int to){
	dis[root] = 0;
	seg.update(b[root].S, 0);
	for (int i=0;i<n;i++){
		if (a[i][2]==root) continue;
		int u = 1+seg.get(a[i][0], a[i][1]+1);
		dis[a[i][2]] = u;
		seg.update(a[i][1], u);
	}
	return dis[to];
}

int32_t main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> n >> q;
	a.resize(n);
	map<int,int> mp;
	for (int i=0;i<n;i++){
		int s, e; cin >> s >> e;
		mp[s]; mp[e];
		b[i] = {s, e};
	}
	int cnt = 0;
	for (auto &it : mp) {
		it.S = cnt++;
	}
	for (int i=0;i<n;i++){
		b[i] = {mp[b[i].F], mp[b[i].S]};
		a[i] = {b[i].F, b[i].S, i};
	}
	sort(all(a),cmp);
	while (q--){
		int s, e;
		cin >> s >> e;
		s--;e--;
		memset(dis, 0x3f, sizeof(dis));
		seg.init();
		int ans = solve(s, e);
		if (ans>n) cout << "impossible\n";
		else cout << ans << endl;
	}
}

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 3672 KB Output is correct
3 Correct 19 ms 3416 KB Output is correct
4 Correct 17 ms 3580 KB Output is correct
5 Correct 17 ms 3416 KB Output is correct
6 Correct 15 ms 3416 KB Output is correct
7 Correct 22 ms 3420 KB Output is correct
8 Correct 21 ms 3416 KB Output is correct
9 Correct 11 ms 3416 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 3672 KB Output is correct
3 Correct 19 ms 3416 KB Output is correct
4 Correct 17 ms 3580 KB Output is correct
5 Correct 17 ms 3416 KB Output is correct
6 Correct 15 ms 3416 KB Output is correct
7 Correct 22 ms 3420 KB Output is correct
8 Correct 21 ms 3416 KB Output is correct
9 Correct 11 ms 3416 KB Output is correct
10 Correct 1 ms 3416 KB Output is correct
11 Correct 1 ms 3420 KB Output is correct
12 Correct 18 ms 3416 KB Output is correct
13 Correct 14 ms 3416 KB Output is correct
14 Correct 16 ms 3416 KB Output is correct
15 Correct 15 ms 3672 KB Output is correct
16 Correct 23 ms 3416 KB Output is correct
17 Correct 21 ms 3416 KB Output is correct
18 Correct 11 ms 3416 KB Output is correct
19 Execution timed out 1547 ms 3908 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 3672 KB Output is correct
3 Correct 19 ms 3416 KB Output is correct
4 Correct 17 ms 3580 KB Output is correct
5 Correct 17 ms 3416 KB Output is correct
6 Correct 15 ms 3416 KB Output is correct
7 Correct 22 ms 3420 KB Output is correct
8 Correct 21 ms 3416 KB Output is correct
9 Correct 11 ms 3416 KB Output is correct
10 Correct 1 ms 3416 KB Output is correct
11 Correct 1 ms 3416 KB Output is correct
12 Correct 18 ms 3416 KB Output is correct
13 Correct 15 ms 3416 KB Output is correct
14 Correct 16 ms 3576 KB Output is correct
15 Correct 14 ms 3416 KB Output is correct
16 Correct 23 ms 3416 KB Output is correct
17 Correct 21 ms 3416 KB Output is correct
18 Correct 10 ms 3416 KB Output is correct
19 Correct 1462 ms 9552 KB Output is correct
20 Correct 1209 ms 9296 KB Output is correct
21 Correct 1263 ms 9296 KB Output is correct
22 Correct 1107 ms 11024 KB Output is correct
23 Execution timed out 1508 ms 15952 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 30.0

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