Submission #125860

#	Time	Username	Problem	Language	Result	Execution time	Memory
125860		tselmegkh	Exhibition (JOI19_ho_t2)	C++14	100 / 100	292 ms	5100 KiB

joi2019_ho_t2

#include<bits/stdc++.h>
using namespace std;

#define INF 1e9
#define MAX 100005
#define xx first
#define yy second
#define pb push_back
#define mp make_pair
#define ull long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define nl '\n'
#define zai <<' '<<
#define all(a) a.begin(),a.end()
#define pc __builtin_popcount
#define debug(args...)  cerr << #args << " = "; Dbg,args; cerr << nl;
struct Dbg { template<typename T> Dbg& operator,(const T& v) { cerr << v << ", "; return *this; } } Dbg;
template <typename T> ostream& operator<<(ostream& _o_, const vector<T>& _v_){
if(!_v_.empty()){_o_<<'[';copy(_v_.begin(),_v_.end(),ostream_iterator<T>(_o_,", "));_o_<<"\b\b]";}return _o_;}
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef priority_queue<int, vector<int>, greater<int>> minheap;
template<class C> void mini(C &_a, C _b) { _a = min(_a, _b); }
template<class C> void maxi(C &_a, C _b) { _a = max(_a, _b); }

vii a;
vi b;
int n, m;

bool check(int x){
    minheap q;
    int j = 0, left = -1;
    bool ok = 1;
    for(int i = m - x; i < m; i++){
       while(j < n && a[j].first <= b[i]){
            if(a[j].second >= left)q.push(a[j].second);
            j++;
       }
       if(q.empty())return 0;
       left = q.top();
       q.pop();
    }
    return 1;
}
vi scn(int n){
    vi a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    return a;
}
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        int c, v;
        cin >> c >> v;
        a.emplace_back(c, v);
    }
    b = scn(m);
    sort(all(a)); sort(all(b));

    int l = 0, r = min(n, m);

    while(l != r){
        int mid = (l + r + 1) >> 1;
        if(check(mid)){
            l = mid;
        }
        else{
            r = mid - 1;
        }
    }
    cout << l;

	return 0;
}

Compilation message (stderr)

joi2019_ho_t2.cpp: In function 'bool check(int)':
joi2019_ho_t2.cpp:34:10: warning: unused variable 'ok' [-Wunused-variable]
     bool ok = 1;
          ^~

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