Submission #362804

#	Time	Username	Problem	Language	Result	Execution time	Memory
362804		Pety	Exhibition (JOI19_ho_t2)	C++14	100 / 100	918 ms	9668 KiB

joi2019_ho_t2

#include <bits/stdc++.h>


using namespace std;

int n, m;
struct painting {
  int s, value;
  bool operator < (const painting &a) const {
    return s < a.s;
  }
} v[100002];
int pref[100002], c[100002];

bool check (int x) {
  int p = 1;
  multiset<int>s;
  int last = 0;
  for (int i = x; i >= 1; i--) {
    while (p <= pref[i]) {
      s.insert(v[p].value);
      p++;
    }
    if (s.empty())
      return 0;
    else {
      auto it = s.lower_bound(last);
      if (it == s.end())
        return 0;
      last = *it;
      s.erase(it);
    }
  }
  return 1;
}

int main ()
{
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> v[i].s >> v[i].value;
  }
  sort(v + 1, v + n + 1);
  for (int i = 1; i <= m; i++)
    cin >> c[i];
  sort(c + 1, c + m + 1, greater<int>());
  int p = 1;
  for (int i = m; i >= 1; i--) {
    while (p <= n && v[p].s <= c[i])
      p++;
    pref[i] = p - 1;
  }
  int st = 1, dr = m, ans = 0;
  while (st <= dr) {
    int mij = (st + dr) / 2;
    if (check(mij)) {
      st = mij + 1;
      ans = mij;
    }
    else
      dr = mij - 1;
  }
  cout << ans;
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50