Submission #721097

#	Time	Username	Problem	Language	Result	Execution time	Memory
721097		gagik_2007	Event Hopping (BOI22_events)	C++17	0 / 100	389 ms	65932 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 {
	int l, r;
	int ind;
	bool st;
	Point(int _l, int _r, bool _st, int i) :l(_l), r(_r), st(_st), ind(i) {}
	bool operator<(const Point& other) const {
		int m1 = (st ? l : r);
		int 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<int, int> vl;
	Vertex* l, * r;
	Vertex(pair<int, int> 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;
int ls[N], rs[N];
int up[N][LG];
Vertex* root = new Vertex({ MOD,MOD });
unordered_map<int, multiset<pair<int,int>>>d;

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

void update(Vertex* v, int tl, int tr, int ind, pair<int, int> vl) {
	//cout << tl << " " << tr << endl;
	//cout << (v->vl.ff) << endl;
	if (tl == tr) {
		v->vl = vl;
	}
	else {
		int 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<int, int> get_min(Vertex* v, int tl, int tr, int l, int r) {
	if (l > r || !v)return { MOD,MOD };
	if (tl == l && tr == r) {
		return get_value(v);
	}
	else {
		int 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 (int i = 0; i < n; i++) {
		int 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 (int 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 (int i = 0; i < n; i++) {
		cout << up[i][0] << " ";
	}
	cout << endl;*/
	for (int i = 0; i < n; i++) {
		for (int j = 1; j < LG; j++) {
			up[i][j] = up[up[i][j - 1]][j - 1];
			//cout << up[i][j] << " ";
		}
		//cout << endl;
	}
	for (int i = 0; i < m; i++) {
		int 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 {
			int res = 0;
			for (int j = LG - 1; j >= 0; j--) {
				if (ls[up[r][j]] > rs[l]) {
					r = up[r][j];
					res += (1 << j);
				}
			}
			res++;
			res++;
			cout << res << endl;
		}
	}
}

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

Compilation message (stderr)

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

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