Submission #1052588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052588		juicy	Matryoshka (JOI16_matryoshka)	C++17	100 / 100	148 ms	17604 KiB

matryoshka

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5;

int n, q;
int ft[N], dp[N], res[N];
array<int, 2> pt[N];

void upd(int i, int x) {
  for (; i <= n; i += i & -i) {
    ft[i] = max(ft[i], x);
  }
}

int qry(int i) {
  int res = 0;
  for (; i; i -= i & -i) {
    res = max(res, ft[i]);
  }
  return res;
}

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

  cin >> n >> q;
  vector<int> comp;
  for (int i = 1; i <= n; ++i) {
    cin >> pt[i][0] >> pt[i][1];
    comp.push_back(pt[i][1]);
  }
  sort(pt + 1, pt + n + 1, [&](const auto &a, const auto &b) {
    return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0];
  });
  sort(comp.begin(), comp.end());
  comp.erase(unique(comp.begin(), comp.end()), comp.end());
  for (int i = 1; i <= n; ++i) {
    pt[i][1] = lower_bound(comp.begin(), comp.end(), pt[i][1]) - comp.begin() + 1;
    dp[i] = qry(pt[i][1]) + 1;
    upd(pt[i][1], dp[i]);
  }
  vector<array<int, 3>> queries;
  for (int i = 1; i <= q; ++i) {
    int a, b; cin >> a >> b;
    queries.push_back({a, b, i});
  }
  sort(queries.begin(), queries.end(), [&](const auto &a, const auto &b) {
    return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0];
  });
  fill(ft + 1, ft + n + 1, 0);
  for (int i = 0, j = 1; i < q; ++i) {
    while (j <= n && pt[j][0] >= queries[i][0]) {
      upd(pt[j][1], dp[j]);
      ++j;
    }
    int k = upper_bound(comp.begin(), comp.end(), queries[i][1]) - comp.begin();
    res[queries[i][2]] = qry(k);
  } 
  for (int i = 1; i <= q; ++i) {
    cout << res[i] << "\n";
  }
  return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 49 / 49