oj.uz

Submission #362803

# Submission time Handle Problem Language Result Execution time Memory
362803 2021-02-04T11:56:46 Z Pety Exhibition (JOI19_ho_t2) C++14
0 / 100
 1 ms 364 KB 
#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() || *s.begin() < last)
      return 0;
    else {
      last = *s.begin();
      s.erase(s.begin());
    }
  }
  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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Incorrect 1 ms 364 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Incorrect 1 ms 364 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Incorrect 1 ms 364 KB Output isn't correct
6 Halted 0 ms 0 KB -