Submission #1359436

#TimeUsernameProblemLanguageResultExecution timeMemory
1359436thewizardmantrapezoid (balkan11_trapezoid)C++20
62 / 100
57 ms5940 KiB
#include <bits/stdc++.h>
using namespace std;

int n;
array<int, 2> mem[100005], fw[100005];
vector<int> vals;
vector<array<int, 3>> v;

void mg(array<int, 2> &a, array<int, 2> b) {
  if (a[0] <= b[0]) {
    if (a[0] < b[0]) a = b;
    else a[1] += b[1], a[1] %= 30013;
  }
}

void update(int i, array<int, 2> val) {
  for (; i < vals.size(); i = i | (i+1)) mg(fw[i], val);
}

array<int, 2> query(int i) {
  array<int, 2> ret = {0, 1};
  for (; i >= 0; i = (i & (i+1)) - 1) mg(ret, fw[i]);
  return ret;
}

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++) {
    int a, b, c, d; cin >> a >> b >> c >> d;
    v.push_back({c, -i-1, a});
    v.push_back({d, i+1, b});
    vals.push_back(a);
    vals.push_back(b);
  }
  sort(vals.begin(), vals.end());
  vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
  sort(v.begin(), v.end());
  for (int i = 0; i < v.size(); i++) v[i][2] = lower_bound(vals.begin(), vals.end(), v[i][2]) - vals.begin();

  for (auto [p, e, u]: v) {
    // cout << p << ' ' << e << ' ' << u << '\n';
    if (e > 0) update(u, mem[e]);
    else mem[-e] = query(u-1), ++mem[-e][0];
  }

  auto [a, b] = query(vals.size() - 1);
  cout << a << ' ' << b << '\n';
}
#Result Execution timeMemoryGrader output
Fetching results...