Submission #699039

#	Time	Username	Problem	Language	Result	Execution time	Memory
699039		Richem	Exhibition (JOI19_ho_t2)	C++14	0 / 100	1 ms	312 KiB

joi2019_ho_t2

#include <iostream>
#include <queue>
#include <algorithm>
#define int long long
using namespace std;

const int MAX_TABLEAU = 1e5+42;

int nbTableau, nbCadre;

pair<int, int> tableau[MAX_TABLEAU];
int cadre[MAX_TABLEAU];

void input() {
    cin >> nbTableau >> nbCadre;

    for(int i = 0; i < nbTableau; i++) {
        cin >> tableau[i].first >> tableau[i].second;
    }
    sort(tableau, tableau + nbTableau);

    for(int i = 0; i < nbCadre; i++) {
        cin >> cadre[i];
    }
    sort(cadre, cadre + nbCadre);
}

bool possible(int k) {
    int curId = 0;

    priority_queue<int> q;
    int preced = 0;
    for(int curCadre = nbCadre-k; curCadre < nbCadre; curCadre++) {
        while(curId < nbTableau && tableau[curId].first <= cadre[curCadre]) {
            q.push(-tableau[curId++].second);
        }

        if(q.size() == 0 || preced > abs(q.top())) {
            return 0;
        }
        preced = abs(q.top());
    }

    return 1;
}

int dicho() {
    int deb = 0, fin = min(nbCadre, nbTableau);

    while(deb < fin) {
        int milieu = (deb + fin+1) / 2;

        if(possible(milieu)) {
            deb = milieu;
        }
        else {
            fin = milieu-1;
        }
    }

    return deb;
}

signed main() {
    input();

    cout << dicho();
}

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