Submission #878766

#	Time	Username	Problem	Language	Result	Execution time	Memory
878766		niter	Exhibition (JOI19_ho_t2)	C++14	100 / 100	217 ms	7724 KiB

joi2019_ho_t2

#include <bits/stdc++.h>
#define pb push_back
#define ins isnert
#define pii pair<int,int>
#define ff first
#define ss second
#define loop(i,a,b) for(int i = (a); i < (b); i ++)
#define op(x) cerr << #x << " = " << x << endl;
#define opa(x) cerr << #x << " = " << x << ", ";
#define ops(x) cerr << x;
#define spac cerr << ' ';
#define entr cerr << endl;
#define STL(x) cerr << #x << " : "; for(auto &qwe:x) cerr << qwe << ' '; cerr << endl;
#define ARR(x, nnn) cerr << #x << " : "; loop(qwe,0,nnn) cerr << x[qwe] << ' '; cerr << endl;
#define BAE(x) (x).begin(), (x).end()
using namespace std;

const int mxn = (int)(1e5) + 10;
struct P{
    int sz, val;
    void read(){
        cin >> sz >> val;
    }
    bool operator<(P x){
        return sz < x.sz;
    }
}a[mxn];
int b[mxn];
vector<int> can_val[mxn];

bool check(int n, int m, int start){
    priority_queue<int, vector<int>, greater<int>> pq;
    int pre = -1;
    loop(i,1,start){
        for(auto &j:can_val[i]){
            pq.push(j);
        }
    }
    bool now_can;
    loop(i,start,m+1){
        now_can = false;
        for(auto &j:can_val[i]){
            pq.push(j);
        }
        while(!pq.empty()){
            if(pq.top() < pre) pq.pop();
            else{
                now_can = true;
                pre = pq.top();
                pq.pop();
                break;
            }
        }
        if(!now_can) return false;
    }
    return true;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m;
    cin >> n >> m;
    loop(i,1,n+1){
        a[i].read();
    }
    sort(a + 1, a + (n + 1));
    loop(i,1,m+1){
        cin >> b[i];
    }
    sort(b + 1, b + (m + 1));
    bool have_ans = false;
    for(int i = 1, j = 1; i <= n && j <= m; ){
//        opa(i) op(j)
        if(a[i].sz <= b[j]){
            can_val[j].pb(a[i].val);
            i++;
            have_ans = true;
        }
        else j++;
    }
    if(!have_ans){
        cout << "0\n";
        return 0;
    }
    int l = 1, r = m, mid;
    while(l < r){
        mid = (l + r) >> 1;
        if(check(n, m, mid)){
            r = mid;
        }
        else{
            l = mid + 1;
        }
    }
    cout << m - l + 1 << '\n';
}

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