oj.uz

Submission #699042

# Submission time Handle Problem Language Result Execution time Memory
699042 2023-02-15T12:24:25 Z Richem Exhibition (JOI19_ho_t2) C++14
0 / 100
 1 ms 212 KB 
#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());
        q.pop();
    }

    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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 0 ms 212 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 0 ms 212 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -