Submission #721334

#	Time	Username	Problem	Language	Result	Execution time	Memory
721334		gagik_2007	Event Hopping (BOI22_events)	C++17	100 / 100	627 ms	107984 KiB

events

#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 Point {
	ll l, r;
	ll ind;
	bool st;
	Point(ll _l, ll _r, bool _st, ll i) :l(_l), r(_r), st(_st), ind(i) {}
	bool operator<(const Point& 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<Point>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);
	//freopen("in.txt", "r", stdin);
	cin >> n >> m;
	for (ll i = 0; i < n; i++) {
		ll l, r;
		cin >> l >> r;
		a.push_back(Point(l, r, true, i));
		a.push_back(Point(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 j = 1; j < LG; j++) {
		for (ll i = 0; i < n; i++) {
			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;
			//cout << up[r][0] << " " << ls[up[r][0]] << " "
			//	<< up[r][LG - 1] << " " << ls[up[r][LG - 1]] << endl;
			//cout << l << " " << ls[l] << " " << rs[l] << 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++;
			res++;
			cout << res << endl;
		}
	}
}

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

Compilation message (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30