oj.uz

Submission #849322

# Submission time Handle Problem Language Result Execution time Memory
849322 2023-09-14T13:31:23 Z vjudge1 Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 38792 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#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 = 1e6 + 15;
const ll inf = 1e18;
int n,q;
int dis[N];
struct segtree{
	static const int off = (1<<20);
	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++){
		//cout << a[i][0] << ' ' << a[i][1] << ' ' << a[i][2] << endl;
		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);
		for (int i=0;i<n;i++){
			//cout << dis[i] << ' ' ;
		}
		if (ans>n) cout << "impossible\n";
		else cout << ans << endl;
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 25692 KB Output is correct
2 Execution timed out 1546 ms 38792 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25692 KB Output is correct
2 Correct 10 ms 25692 KB Output is correct
3 Correct 181 ms 25948 KB Output is correct
4 Correct 179 ms 25948 KB Output is correct
5 Correct 185 ms 25920 KB Output is correct
6 Correct 181 ms 25948 KB Output is correct
7 Correct 192 ms 25996 KB Output is correct
8 Correct 180 ms 26000 KB Output is correct
9 Correct 169 ms 25860 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25692 KB Output is correct
2 Correct 10 ms 25692 KB Output is correct
3 Correct 181 ms 25948 KB Output is correct
4 Correct 179 ms 25948 KB Output is correct
5 Correct 185 ms 25920 KB Output is correct
6 Correct 181 ms 25948 KB Output is correct
7 Correct 192 ms 25996 KB Output is correct
8 Correct 180 ms 26000 KB Output is correct
9 Correct 169 ms 25860 KB Output is correct
10 Correct 6 ms 25692 KB Output is correct
11 Correct 11 ms 25828 KB Output is correct
12 Correct 179 ms 25948 KB Output is correct
13 Correct 171 ms 25948 KB Output is correct
14 Correct 186 ms 25692 KB Output is correct
15 Correct 176 ms 25928 KB Output is correct
16 Correct 176 ms 25996 KB Output is correct
17 Correct 183 ms 25948 KB Output is correct
18 Correct 177 ms 25948 KB Output is correct
19 Execution timed out 1566 ms 26652 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 25692 KB Output is correct
2 Correct 10 ms 25692 KB Output is correct
3 Correct 181 ms 25948 KB Output is correct
4 Correct 179 ms 25948 KB Output is correct
5 Correct 185 ms 25920 KB Output is correct
6 Correct 181 ms 25948 KB Output is correct
7 Correct 192 ms 25996 KB Output is correct
8 Correct 180 ms 26000 KB Output is correct
9 Correct 169 ms 25860 KB Output is correct
10 Correct 5 ms 25688 KB Output is correct
11 Correct 10 ms 25692 KB Output is correct
12 Correct 189 ms 25928 KB Output is correct
13 Correct 177 ms 25944 KB Output is correct
14 Correct 165 ms 25948 KB Output is correct
15 Correct 165 ms 25948 KB Output is correct
16 Correct 169 ms 25944 KB Output is correct
17 Correct 165 ms 25948 KB Output is correct
18 Correct 167 ms 25856 KB Output is correct
19 Execution timed out 1557 ms 38752 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 1548 ms 38740 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 25692 KB Output is correct
2 Execution timed out 1546 ms 38792 KB Time limit exceeded
3 Halted 0 ms 0 KB -