Submission #721017

#TimeUsernameProblemLanguageResultExecution timeMemory
721017gagik_2007Event Hopping (BOI22_events)C++17
Compilation error
0 ms0 KiB
#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: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)
      |     ^~~~