Submission #1145440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145440		dnialh	Mostovi (COI14_mostovi)	C++20	100 / 100	273 ms	9940 KiB

mostovi

#include <vector>
#include <set>
#include <tuple>
#include <iostream>
#include <algorithm>
#include <map>
#include <cassert>

using namespace std;

int main () {
  int n, q; cin >> n >> q;

  set<int> top; top.insert(n); top.insert(0);
  set<int> bot; bot.insert(n + 1); bot.insert(2 * n + 1);
  map<int, int> down; down[n + 1] = -1; down[0] = -1;
  map<int, int> up; up[n] = -1; up[2 * n + 1] = -1;

  for (int i = 0; i < q; i++) {
    char ty; cin >> ty;
    int u, v; cin >> u >> v;

    if (ty == 'A') {
      if (u > v) swap(u, v);
      assert (u <= n);
      assert (v > n);

      down[u] = v;
      up[v] = u;
    } else if (ty == 'B') {
      if (u > v) swap(u, v);
      assert (v == u + 1);

      if (u <= n) {
        top.insert(u);
      } else {
        bot.insert(v);
      }
    } else {
      assert (ty == 'Q');

      auto find_jump = [&n, &top, &bot, &down, &up](int u) {
          if (u <= n) {
            int cut = *top.lower_bound(u);
            auto [j1, j2] = *down.lower_bound(u);

            if (j1 > cut) return -1;

            return j2;
          } else {
            int cut = *prev(bot.upper_bound(u));
            auto [j1, j2] = *prev(up.upper_bound(u));

            if (j1 < cut) return -1;

            return j2;
          }
      };

      auto find_jump_rev = [&n, &top, &bot, &down, &up](int u) {
          if (u <= n) {
            int cut = *prev(top.lower_bound(u));
            auto [j1, j2] = *prev(down.upper_bound(u));

            if (j1 <= cut) return -1;

            return j2;
          } else {
            int cut = *bot.upper_bound(u);
            auto [j1, j2] = *up.lower_bound(u);

            if (j1 >= cut) return -1;

            return j2;
          }
      };


      auto query = [&n, &top, &bot, &down, &up, &find_jump, &find_jump_rev](auto &rec, int u, int v) {
        if ((u <= n) != (v <= n)) {
          int j = find_jump(u);
          if (j == -1) return false;
          return rec(rec, j, v);
        }

        if (u <= n) {
          assert (v <= n);
          if (u <= v) {
            int cut = *top.lower_bound(u);
            return cut >= v;
          } else {
            int j1 = find_jump(u);
            int j2 = find_jump_rev(v);

            if (j1 == -1 || j2 == -1) return false;
            assert (j1 >= j2);

            return rec(rec, j1, j2);
          }
        }

        if (u >= n) {
          assert (v >= n);
          if (u >= v) {
            int cut = *prev(bot.upper_bound(u));
            return cut <= v;
          } else {
            int j1 = find_jump(u);
            int j2 = find_jump_rev(v);

            if (j1 == -1 || j2 == -1) return false;
            assert (j1 <= j2);

            return rec(rec, j1, j2);
          }
        }

        assert (0);
      };

      bool out = query(query, u, v);
      if (out) {
        cout << "DA\n";
      } else {
        cout << "NE\n";
      }
    }
  }
}

• Subtask 1: 100 / 100