Submission #721017

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
721017	2023-04-10T06:07:15 Z	gagik_2007	Event Hopping (BOI22_events)	C++17	Compilation error	0 ms	0 KB

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

events.cpp:1:20: warning: extra tokens at end of #include directive
    1 | #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;
      |                    ^
events.cpp:3:2: error: ISO C++ forbids declaration of 'Point' with no type [-fpermissive]
    3 |  Point(int _l, int _r, bool _st, int i) :l(_l), r(_r), st(_st), ind(i) {}
      |  ^~~~~
events.cpp: In function 'int Point(int, int, bool, int)':
events.cpp:3:42: error: only constructors take member initializers
    3 |  Point(int _l, int _r, bool _st, int i) :l(_l), r(_r), st(_st), ind(i) {}
      |                                          ^
events.cpp:3:73: warning: no return statement in function returning non-void [-Wreturn-type]
    3 |  Point(int _l, int _r, bool _st, int i) :l(_l), r(_r), st(_st), ind(i) {}
      |                                                                         ^
events.cpp: At global scope:
events.cpp:4:23: error: 'Point' does not name a type
    4 |  bool operator<(const Point& other) const {
      |                       ^~~~~
events.cpp:4:37: error: non-member function 'bool operator<(const int&)' cannot have cv-qualifier
    4 |  bool operator<(const Point& other) const {
      |                                     ^~~~~
events.cpp:4:7: error: 'bool operator<(const int&)' must have an argument of class or enumerated type
    4 |  bool operator<(const Point& other) const {
      |       ^~~~~~~~
events.cpp:13:1: error: expected declaration before '}' token
   13 | };
      | ^
events.cpp:16:2: error: 'pair' does not name a type
   16 |  pair<int, int> vl;
      |  ^~~~
events.cpp:18:13: error: expected ')' before '<' token
   18 |  Vertex(pair<int, int> value) :vl(value),l(nullptr),r(nullptr) {}
      |        ~    ^
      |             )
events.cpp:21:1: error: 'll' does not name a type
   21 | ll ttt;
      | ^~
events.cpp:22:7: error: 'll' does not name a type
   22 | const ll INF = 1e18;
      |       ^~
events.cpp:23:7: error: 'll' does not name a type
   23 | const ll MOD = 1e9 + 7;
      |       ^~
events.cpp:24:7: error: 'll' does not name a type
   24 | const ll N = 100007;
      |       ^~
events.cpp:25:7: error: 'll' does not name a type
   25 | const ll LG = 23;
      |       ^~
events.cpp:26:1: error: 'll' does not name a type
   26 | ll n, m, k;
      | ^~
events.cpp:27:1: error: 'vector' does not name a type
   27 | vector<Point>a;
      | ^~~~~~
events.cpp:28:8: error: 'N' was not declared in this scope
   28 | int ls[N], rs[N];
      |        ^
events.cpp:28:15: error: 'N' was not declared in this scope
   28 | int ls[N], rs[N];
      |               ^
events.cpp:29:8: error: 'N' was not declared in this scope
   29 | int up[N][LG];
      |        ^
events.cpp:29:11: error: 'LG' was not declared in this scope
   29 | int up[N][LG];
      |           ^~
events.cpp:30:29: error: 'MOD' was not declared in this scope
   30 | Vertex* root = new Vertex({ MOD,MOD });
      |                             ^~~
events.cpp:30:33: error: 'MOD' was not declared in this scope
   30 | Vertex* root = new Vertex({ MOD,MOD });
      |                                 ^~~
events.cpp:30:38: error: could not convert '{<expression error>, <expression error>}' from '<brace-enclosed initializer list>' to 'Vertex'
   30 | Vertex* root = new Vertex({ MOD,MOD });
      |                                      ^
      |                                      |
      |                                      <brace-enclosed initializer list>
events.cpp:31:1: error: 'unordered_map' does not name a type
   31 | unordered_map<int, multiset<pair<int,int>>>d;
      | ^~~~~~~~~~~~~
events.cpp:33:1: error: 'pair' does not name a type
   33 | pair<int,int> get_value(Vertex* v) {
      | ^~~~
events.cpp:38:49: error: 'pair' has not been declared
   38 | void update(Vertex* v, int tl, int tr, int ind, pair<int, int> vl) {
      |                                                 ^~~~
events.cpp:38:53: error: expected ',' or '...' before '<' token
   38 | void update(Vertex* v, int tl, int tr, int ind, pair<int, int> vl) {
      |                                                     ^
events.cpp: In function 'void update(Vertex*, int, int, int, int)':
events.cpp:42:6: error: 'struct Vertex' has no member named 'vl'; did you mean 'l'?
   42 |   v->vl = vl;
      |      ^~
      |      l
events.cpp:42:11: error: 'vl' was not declared in this scope; did you mean 'v'?
   42 |   v->vl = vl;
      |           ^~
      |           v
events.cpp:48:25: error: 'MOD' was not declared in this scope
   48 |     v->l = new Vertex({ MOD,MOD });
      |                         ^~~
events.cpp:48:34: error: could not convert '{<expression error>, MOD}' from '<brace-enclosed initializer list>' to 'Vertex'
   48 |     v->l = new Vertex({ MOD,MOD });
      |                                  ^
      |                                  |
      |                                  <brace-enclosed initializer list>
events.cpp:50:30: error: 'vl' was not declared in this scope; did you mean 'v'?
   50 |    update(v->l, tl, tm, ind, vl);
      |                              ^~
      |                              v
events.cpp:54:25: error: 'MOD' was not declared in this scope
   54 |     v->r = new Vertex({ MOD,MOD });
      |                         ^~~
events.cpp:54:34: error: could not convert '{<expression error>, MOD}' from '<brace-enclosed initializer list>' to 'Vertex'
   54 |     v->r = new Vertex({ MOD,MOD });
      |                                  ^
      |                                  |
      |                                  <brace-enclosed initializer list>
events.cpp:56:34: error: 'vl' was not declared in this scope; did you mean 'v'?
   56 |    update(v->r, tm + 1, tr, ind, vl);
      |                                  ^~
      |                                  v
events.cpp:58:6: error: 'struct Vertex' has no member named 'vl'; did you mean 'l'?
   58 |   v->vl = min(get_value(v->l), get_value(v->r));
      |      ^~
      |      l
events.cpp:58:15: error: 'get_value' was not declared in this scope
   58 |   v->vl = min(get_value(v->l), get_value(v->r));
      |               ^~~~~~~~~
events.cpp:58:11: error: 'min' was not declared in this scope; did you mean 'std::min'?
   58 |   v->vl = min(get_value(v->l), get_value(v->r));
      |           ^~~
      |           std::min
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from events.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: 'std::min' declared here
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
events.cpp: At global scope:
events.cpp:62:1: error: 'pair' does not name a type
   62 | pair<int, int> get_min(Vertex* v, int tl, int tr, int l, int r) {
      | ^~~~
events.cpp: In function 'int main()':
events.cpp:75:2: error: 'ios_base' has not been declared
   75 |  ios_base::sync_with_stdio(false);
      |  ^~~~~~~~
events.cpp:76:2: error: 'cin' was not declared in this scope; did you mean 'std::cin'?
   76 |  cin.tie(0);
      |  ^~~
      |  std::cin
In file included from events.cpp:1:
/usr/include/c++/10/iostream:60:18: note: 'std::cin' declared here
   60 |   extern istream cin;  /// Linked to standard input
      |                  ^~~
events.cpp:77:2: error: 'cout' was not declared in this scope; did you mean 'std::cout'?
   77 |  cout.tie(0);
      |  ^~~~
      |  std::cout
In file included from events.cpp:1:
/usr/include/c++/10/iostream:61:18: note: 'std::cout' declared here
   61 |   extern ostream cout;  /// Linked to standard output
      |                  ^~~~
events.cpp:78:9: error: 'n' was not declared in this scope
   78 |  cin >> n >> m;
      |         ^
events.cpp:78:14: error: 'm' was not declared in this scope; did you mean 'tm'?
   78 |  cin >> n >> m;
      |              ^
      |              tm
events.cpp:82:3: error: 'a' was not declared in this scope
   82 |   a.push_back(Point(l, r, true, i));
      |   ^
events.cpp:84:3: error: 'ls' was not declared in this scope; did you mean 'l'?
   84 |   ls[i] = l;
      |   ^~
      |   l
events.cpp:85:3: error: 'rs' was not declared in this scope; did you mean 'r'?
   85 |   rs[i] = r;
      |   ^~
      |   r
events.cpp:87:7: error: 'a' was not declared in this scope
   87 |  sort(a.begin(), a.end());
      |       ^
events.cpp:87:2: error: 'sort' was not declared in this scope; did you mean 'qsort'?
   87 |  sort(a.begin(), a.end());
      |  ^~~~
      |  qsort
events.cpp:90:4: error: 'd' was not declared in this scope
   90 |    d[a[i].r].insert({ a[i].l,a[i].ind });
      |    ^
events.cpp:91:20: error: 'MOD' was not declared in this scope
   91 |    update(root, 0, MOD - 1, a[i].r, *d[a[i].r].begin());
      |                    ^~~
events.cpp:92:4: error: 'up' was not declared in this scope
   92 |    up[a[i].ind][0] = get_min(root, 0, MOD - 1, 0, a[i].r).ss;
      |    ^~
events.cpp:92:22: error: 'get_min' was not declared in this scope
   92 |    up[a[i].ind][0] = get_min(root, 0, MOD - 1, 0, a[i].r).ss;
      |                      ^~~~~~~
events.cpp:95:4: error: 'd' was not declared in this scope
   95 |    d[a[i].r].erase(d[a[i].r].find({ a[i].l,a[i].ind }));
      |    ^
events.cpp:96:42: error: 'MOD' was not declared in this scope
   96 |    if (d[a[i].r].empty())update(root, 0, MOD - 1, a[i].r, { MOD,MOD });
      |                                          ^~~
events.cpp:98:21: error: 'MOD' was not declared in this scope
   98 |     update(root, 0, MOD - 1, a[i].r, *d[a[i].r].begin());
      |                     ^~~
events.cpp:107:23: error: 'LG' was not declared in this scope
  107 |   for (int j = 1; j < LG; j++) {
      |                       ^~
events.cpp:108:4: error: 'up' was not declared in this scope
  108 |    up[i][j] = up[up[i][j - 1]][j - 1];
      |    ^~
events.cpp:117:7: error: 'rs' was not declared in this scope; did you mean 'r'?
  117 |   if (rs[l] > rs[r]) {
      |       ^~
      |       r
events.cpp:118:28: error: 'endl' was not declared in this scope; did you mean 'std::endl'?
  118 |    cout << "impossible" << endl;
      |                            ^~~~
      |                            std::endl
In file included from /usr/include/c++/10/iostream:39,
                 from events.cpp:1:
/usr/include/c++/10/ostream:681:5: note: 'std::endl' declared here
  681 |     endl(basic_ostream<_CharT, _Traits>& __os)
      |     ^~~~
events.cpp:120:12: error: 'ls' was not declared in this scope; did you mean 'l'?
  120 |   else if (ls[up[r][LG - 1]] > rs[l]) {
      |            ^~
      |            l
events.cpp:120:15: error: 'up' was not declared in this scope
  120 |   else if (ls[up[r][LG - 1]] > rs[l]) {
      |               ^~
events.cpp:120:21: error: 'LG' was not declared in this scope
  120 |   else if (ls[up[r][LG - 1]] > rs[l]) {
      |                     ^~
events.cpp:121:28: error: 'endl' was not declared in this scope; did you mean 'std::endl'?
  121 |    cout << "impossible" << endl;
      |                            ^~~~
      |                            std::endl
In file included from /usr/include/c++/10/iostream:39,
                 from events.cpp:1:
/usr/include/c++/10/ostream:681:5: note: 'std::endl' declared here
  681 |     endl(basic_ostream<_CharT, _Traits>& __os)
      |     ^~~~
events.cpp:124:17: error: 'endl' was not declared in this scope; did you mean 'std::endl'?
  124 |    cout << 0 << endl;
      |                 ^~~~
      |                 std::endl
In file included from /usr/include/c++/10/iostream:39,
                 from events.cpp:1:
/usr/include/c++/10/ostream:681:5: note: 'std::endl' declared here
  681 |     endl(basic_ostream<_CharT, _Traits>& __os)
      |     ^~~~
events.cpp:127:17: error: 'endl' was not declared in this scope; did you mean 'std::endl'?
  127 |    cout << 1 << endl;
      |                 ^~~~
      |                 std::endl
In file included from /usr/include/c++/10/iostream:39,
                 from events.cpp:1:
/usr/include/c++/10/ostream:681:5: note: 'std::endl' declared here
  681 |     endl(basic_ostream<_CharT, _Traits>& __os)
      |     ^~~~
events.cpp:139:19: error: 'endl' was not declared in this scope; did you mean 'std::endl'?
  139 |    cout << res << endl;
      |                   ^~~~
      |                   std::endl
In file included from /usr/include/c++/10/iostream:39,
                 from events.cpp:1:
/usr/include/c++/10/ostream:681:5: note: 'std::endl' declared here
  681 |     endl(basic_ostream<_CharT, _Traits>& __os)
      |     ^~~~