Submission #1317399

#TimeUsernameProblemLanguageResultExecution timeMemory
1317399alan_ctrapezoid (balkan11_trapezoid)C++20
2 / 100
218 ms29388 KiB
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

const int M = 30013;

struct Seg {
  int n;
  vector<pii> t;

  Seg(int n_) : n(n_), t(2 * n, {0, 1}) {}

  pii combine(pii &a, pii &b) {
    if (a.first == b.first)
      return {a.first, (a.second + b.second) % M};
    return a.first < b.first ? b : a;
  }

  void set(int i, pii v) {
    i += n;
    t[i] = combine(t[i], v);
    while (i /= 2)
      t[i] = combine(t[2 * i], t[2 * i + 1]);
  }

  pii query(int l, int r) {
    pii res = {0, 1};
    for (l += n, r += n; l < r; l /= 2, r /= 2) {
      if (l % 2)
        res = combine(res, t[l++]);
      if (r % 2)
        res = combine(res, t[--r]);
    }
    return res;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  vector<array<int, 4>> trap(n);
  vector<int> coord;
  for (auto &[a, b, c, d] : trap) {
    cin >> a >> b >> c >> d;
    coord.insert(coord.end(), {a, b, c, d});
  }

  coord.erase(unique(coord.begin(), coord.end()), coord.end());
  sort(coord.begin(), coord.end());
  int sz = (int)coord.size();
  map<int, int> cc;
  for (int i = 0; i < sz; i++)
    cc[coord[i]] = i;

  vector<array<int, 4>> event;
  for (int i = 0; i < n; i++) {
    event.push_back({cc[trap[i][0]], -cc[trap[i][1]], 0, i});
    event.push_back({cc[trap[i][2]], -cc[trap[i][3]], 1, i});
  }
  sort(event.begin(), event.end());

  Seg seg(sz);
  vector<pii> ans(n);
  for (auto &[x, y, b, i] : event) {
    y = -y;
    if (b) {
      seg.set(y, ans[i]);
    } else {
      auto [v, c] = seg.query(0, y);
      ans[i] = {v + 1, c};
    }
  }
  auto [v, c] = seg.query(0, sz);
  cout << v << ' ' << c << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...