oj.uz

답안 #721298

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
721298 2023-04-10T16:07:32 Z gagik_2007 Event Hopping (BOI22_events) C++17
0 / 100
 524 ms 99948 KB 
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;

typedef long long ll;
typedef long double ld;

#define ff first
#define ss second

struct Poll {
	ll l, r;
	ll ind;
	bool st;
	Poll(ll _l, ll _r, bool _st, ll i) :l(_l), r(_r), st(_st), ind(i) {}
	bool operator<(const Poll& other) const {
		ll m1 = (st ? l : r);
		ll m2 = (other.st ? other.l : other.r);
		if (m1 < m2)return true;
		if (m1 > m2)return false;
		if (st && !other.st)return true;
		if (!st && other.st)return false;
		return false;
	}
};

struct Vertex {
	pair<ll, ll> vl;
	Vertex* l, * r;
	Vertex(pair<ll, ll> value) :vl(value),l(nullptr),r(nullptr) {}
};

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 100007;
const ll LG = 23;
ll n, m, k;
vector<Poll>a;
ll ls[N], rs[N];
ll up[N][LG];
Vertex* root = new Vertex({ MOD,MOD });
unordered_map<ll, multiset<pair<ll,ll>>>d;

pair<ll,ll> get_value(Vertex* v) {
	if (!v)return { MOD,MOD };
	return v->vl;
}

void update(Vertex* v, ll tl, ll tr, ll ind, pair<ll, ll> vl) {
	//cout << tl << " " << tr << endl;
	//cout << (v->vl.ff) << endl;
	if (tl == tr) {
		v->vl = vl;
	}
	else {
		ll tm = (tl + tr) / 2;
		if (ind <= tm) {
			if (!v->l) {
				v->l = new Vertex({ MOD,MOD });
			}
			update(v->l, tl, tm, ind, vl);
		}
		else {
			if (!v->r) {
				v->r = new Vertex({ MOD,MOD });
			}
			update(v->r, tm + 1, tr, ind, vl);
		}
		v->vl = min(get_value(v->l), get_value(v->r));
	}
}

pair<ll, ll> get_min(Vertex* v, ll tl, ll tr, ll l, ll r) {
	if (l > r || !v)return { MOD,MOD };
	if (tl == l && tr == r) {
		return get_value(v);
	}
	else {
		ll tm = (tl + tr) / 2;
		return min(get_min(v->l, tl, tm, l, min(r, tm)),
			get_min(v->r, tm + 1, tr, max(l, tm + 1), r));
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (ll i = 0; i < n; i++) {
		ll l, r;
		cin >> l >> r;
		a.push_back(Poll(l, r, true, i));
		a.push_back(Poll(l, r, false, i));
		ls[i] = l;
		rs[i] = r;
	}
	sort(a.begin(), a.end());
	for (ll i = 0; i < a.size(); i++) {
		if (a[i].st) {
			d[a[i].r].insert({ a[i].l,a[i].ind });
			update(root, 0, MOD - 1, a[i].r, *d[a[i].r].begin());
			up[a[i].ind][0] = get_min(root, 0, MOD - 1, 0, a[i].r).ss;
		}
		else {
			d[a[i].r].erase(d[a[i].r].find({ a[i].l,a[i].ind }));
			if (d[a[i].r].empty())update(root, 0, MOD - 1, a[i].r, { MOD,MOD });
			else {
				update(root, 0, MOD - 1, a[i].r, *d[a[i].r].begin());
			}
		}
	}
	/*for (ll i = 0; i < n; i++) {
		cout << up[i][0] << " ";
	}
	cout << endl;*/
	for (ll i = 0; i < n; i++) {
		for (ll j = 1; j < LG; j++) {
			up[i][j] = up[up[i][j - 1]][j - 1];
			//cout << up[i][j] << " ";
		}
		//cout << endl;
	}
	for (ll i = 0; i < m; i++) {
		ll l, r;
		cin >> l >> r;
		l--, r--;
		if (rs[l] > rs[r]) {
			cout << "impossible" << endl;
		}
		else if (ls[up[r][LG - 1]] > rs[l]) {
			cout << "impossible" << endl;
		}
		else if (l == r) {
			cout << 0 << endl;
		}
		else if (rs[l] >= ls[r]) {
			cout << 1 << endl;
		}
		else {
			ll res = 0;
			for (ll j = LG - 1; j >= 0; j--) {
				if (ls[up[r][j]] > rs[l]) {
					r = up[r][j];
					res += (1ll << j);
				}
			}
			r = up[r][0];
			res++;
			if (ls[r] <= rs[l] && rs[l] <= rs[r]) {
				if (l != r)res++;
				cout << res << endl;
			}
			else {
				assert(false);
				cout << "impossible\n";
			}
		}
	}
}

/// ---- - --------  ------ -------- -- - - -
/// Just a reminder. Ubuntu password is I O I
/// ---- - --------  ------ -------- -- - - -

Compilation message

events.cpp: In constructor 'Poll::Poll(ll, ll, bool, ll)':
events.cpp:32:7: warning: 'Poll::st' will be initialized after [-Wreorder]
   32 |  bool st;
      |       ^~
events.cpp:31:5: warning:   'll Poll::ind' [-Wreorder]
   31 |  ll ind;
      |     ^~~
events.cpp:33:2: warning:   when initialized here [-Wreorder]
   33 |  Poll(ll _l, ll _r, bool _st, ll i) :l(_l), r(_r), st(_st), ind(i) {}
      |  ^~~~
events.cpp: In function 'int main()':
events.cpp:118:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<Poll>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |  for (ll i = 0; i < a.size(); i++) {
      |                 ~~^~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 461 ms 99948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 3 ms 1620 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 3 ms 1620 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 3 ms 1620 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 524 ms 99944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 461 ms 99948 KB Output isn't correct
3 Halted 0 ms 0 KB -