oj.uz

Submission #588855

# Submission time Handle Problem Language Result Execution time Memory
588855 2022-07-04T06:37:13 Z Arnch Event Hopping (BOI22_events) C++17
20 / 100
 403 ms 59100 KB 
// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl
//#define endl '\n'

constexpr ll inf = 1e18, N = 1e6 + 10, Log = 30;

int n, q, s[N], e[N];
int val[N], par[N][Log], rpar[N][Log];

void Compress() {
	vector<int> com;
	for(int i = 0; i < n; i++) {
		com.push_back(s[i]), com.push_back(e[i]);
	}
	sort(All(com)), com.erase(unique(All(com)), com.end());
	for(int i = 0; i < n; i++) {
		s[i] = lower_bound(All(com), s[i]) - com.begin();
		e[i] = lower_bound(All(com), e[i]) - com.begin();
	}
}

struct node {
	int cnt;
	node() {
		cnt = -1;
	}
};
struct Seg {
	node x[N << 2];
	int type;
	Seg(int dio) {
		type = dio;
	}
	void build(int l, int r, int v) {
		x[v].cnt = -1;
		if(r - l < 2) return;
		int mid = (l + r) >> 1;
		build(l, mid, 2 * v), build(mid, r, 2 * v + 1);
	}
	node merge(node a, node b) {
		node res = a;
		if(type == 0) {
			if(b.cnt != -1 && (res.cnt == -1 || e[b.cnt] > e[res.cnt])) res = b;
			return res;
		} else {
			if(b.cnt != -1 && (res.cnt == -1 || e[b.cnt] < e[res.cnt])) res = b;
			return res;
		}
	}
	void change(int l, int r, int ind, int val, int v) {
		if(r - l < 2) {
			if(type == 0) {
				if(x[v].cnt == -1 || e[x[v].cnt] < e[val]) 
					x[v].cnt = val;
			} else {
				if(x[v].cnt == -1 || e[x[v].cnt] > e[val]) 
					x[v].cnt = val;
			}
			return;
		}
		int mid = (l + r) >> 1;
		if(ind < mid) change(l, mid, ind, val, 2 * v);
		else change(mid, r, ind, val, 2 * v + 1);
		x[v] = merge(x[2 * v], x[2 * v + 1]);
	}
	node get(int l, int r, int s, int e, int v) {
		node res;
		if(r <= s || l >= e) return res;
		if(l >= s && r <= e) return x[v];
		int mid = (l + r) >> 1;
		return merge(get(l, mid, s, e, 2 * v), get(mid, r, s, e, 2 * v + 1));
	}
} S(0), E(1);

void Pre1() {
	for(int i = 0; i < n; i++) {
		S.change(0, 2 * n, s[i], i, 1);
	}
	for(int i = 0; i < n; i++) {
		int pos = S.get(0, 2 * n, s[i], e[i] + 1, 1).cnt;
		if(pos != -1 && e[pos] > e[i]) par[i][0] = pos;
		else par[i][0] = -1;
	}
	
	for(int lg = 1; lg < Log; lg++) {
		for(int i = 0; i < n; i++) {
			if(par[i][lg - 1] == -1 || par[par[i][lg - 1]][lg - 1] == -1) {
				par[i][lg] = -1; continue;
			}
			par[i][lg] = par[par[i][lg - 1]][lg - 1];
		}
	}
}
void Pre2() {
	E.build(0, 2 * n, 1);
	for(int i = 0; i < n; i++) {
		E.change(0, 2 * n, e[i], i, 1);
	}
	for(int i = 0; i < n; i++) {
		int pos = E.get(0, 2 * n, s[i], e[i] + 1, 1).cnt;
		if(pos != -1 && s[pos] < s[i]) rpar[i][0] = pos;
		else rpar[i][0] = -1;
	}

	for(int lg = 1; lg < Log; lg++) {
		for(int i = 0; i < n; i++) {
			if(rpar[i][lg - 1] == -1 || rpar[rpar[i][lg - 1]][lg - 1] == -1) {
				rpar[i][lg] = -1; continue;
			}
			rpar[i][lg] = rpar[rpar[i][lg - 1]][lg - 1];
		}
	}
}

int main() {
    ios :: sync_with_stdio(0), cin.tie(0);

	cin >>n >>q;
	for(int i = 0; i < n; i++) {
		cin >>s[i] >>e[i];
	}
	Compress();

	Pre1();
	Pre2();

	for(int i = 0; i < q; i++) {
		int x, y; cin >>x >>y;
		x--, y--;

		if(x != y && e[x] > e[y]) {
			cout<<"impossible" <<endl;
			continue;
		}
		if(x == y) {
			cout<<0 <<endl;
			continue;
		}
		if(e[x] >= s[y] && e[x] <= e[y]) {
			cout<<1 <<endl;
			continue;
		}
		
		int t = 0;
		for(int lg = Log - 1; lg >= 0; lg--) {
			if(par[x][lg] == -1) continue;
			if(e[par[x][lg]] < s[y]) {
				x = par[x][lg];
				t += (1 << lg);
			}
		}
		if(par[x][0] != -1 && e[par[x][0]] <= e[y]) {
			cout<<t + 2 <<endl;
			continue;
		}
		for(int lg = Log - 1; lg >= 0; lg--) {
			if(rpar[y][lg] == -1) continue;
			if(s[rpar[y][lg]] > e[x]) {
				y = rpar[y][lg];
				t += (1 << lg);
			}
		}
		if(rpar[y][0] != -1 && s[rpar[y][0]] <= e[x]) {
			cout<<t + 2 <<endl;
			continue;
		}
		cout<<"impossible" <<endl;
	}

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31572 KB Output is correct
2 Correct 330 ms 56720 KB Output is correct
3 Correct 345 ms 56644 KB Output is correct
4 Correct 367 ms 56628 KB Output is correct
5 Correct 347 ms 56672 KB Output is correct
6 Correct 373 ms 59100 KB Output is correct
7 Incorrect 353 ms 58448 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31612 KB Output is correct
2 Correct 13 ms 31576 KB Output is correct
3 Correct 13 ms 31840 KB Output is correct
4 Correct 13 ms 31832 KB Output is correct
5 Correct 15 ms 31908 KB Output is correct
6 Incorrect 16 ms 31884 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31612 KB Output is correct
2 Correct 13 ms 31576 KB Output is correct
3 Correct 13 ms 31840 KB Output is correct
4 Correct 13 ms 31832 KB Output is correct
5 Correct 15 ms 31908 KB Output is correct
6 Incorrect 16 ms 31884 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31612 KB Output is correct
2 Correct 13 ms 31576 KB Output is correct
3 Correct 13 ms 31840 KB Output is correct
4 Correct 13 ms 31832 KB Output is correct
5 Correct 15 ms 31908 KB Output is correct
6 Incorrect 16 ms 31884 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 56668 KB Output is correct
2 Correct 357 ms 56616 KB Output is correct
3 Correct 363 ms 56700 KB Output is correct
4 Correct 339 ms 57128 KB Output is correct
5 Correct 377 ms 57000 KB Output is correct
6 Correct 403 ms 56752 KB Output is correct
7 Correct 396 ms 56860 KB Output is correct
8 Correct 363 ms 56916 KB Output is correct
9 Correct 213 ms 56072 KB Output is correct
10 Correct 378 ms 56592 KB Output is correct
11 Correct 367 ms 56264 KB Output is correct
12 Correct 365 ms 56368 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31572 KB Output is correct
2 Correct 330 ms 56720 KB Output is correct
3 Correct 345 ms 56644 KB Output is correct
4 Correct 367 ms 56628 KB Output is correct
5 Correct 347 ms 56672 KB Output is correct
6 Correct 373 ms 59100 KB Output is correct
7 Incorrect 353 ms 58448 KB Output isn't correct
8 Halted 0 ms 0 KB -