Submission #174302

#	Time	Username	Problem	Language	Result	Execution time	Memory
174302		AlexLuchianov	Exhibition (JOI19_ho_t2)	C++14	100 / 100	989 ms	9152 KiB

joi2019_ho_t2

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 100000;
struct Picture{
  int sz;
  int value;
  bool operator < (Picture const &a) const{
    return sz < a.sz;
  }
} v[1 + nmax];
int frame[1 + nmax];
int n, m;

int test(int target){
  multiset<int> myset;
  int result = 0, ptr = 1, currvalue = 0;
  for(int i = m - target + 1; i <= m; i++){
    while(ptr <= n && v[ptr].sz <= frame[i])
      myset.insert(v[ptr++].value);
    set<int>::iterator it = myset.lower_bound(currvalue);
    if(it != myset.end()) {
      currvalue = *it;
      myset.erase(it);
    } else
      return 0;
  }
  return 1;
}

int binarysearch(int from, int to){
  if(from < to){
    int mid = (from + to + 1) / 2;
    if(test(mid) == 1)
      return binarysearch(mid, to);
    else
      return binarysearch(from, mid - 1);
  } else
    return from;
}
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  cin >> n >> m;
  for(int i = 1;i <= n; i++)
    cin >> v[i].sz >> v[i].value;
  sort(v + 1, v + n + 1);
  for(int i = 1;i <= m; i++)
    cin >> frame[i];
  sort(frame + 1, frame + m + 1);
  cout << binarysearch(0, MIN(n, m));

  return 0;
}

Compilation message (stderr)

joi2019_ho_t2.cpp: In function 'int test(int)':
joi2019_ho_t2.cpp:25:7: warning: unused variable 'result' [-Wunused-variable]
   int result = 0, ptr = 1, currvalue = 0;
       ^~~~~~

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