oj.uz

Submission #340975

# Submission time Handle Problem Language Result Execution time Memory
340975 2020-12-28T18:48:17 Z ijxjdjd Exhibition (JOI19_ho_t2) C++14
0 / 100
 1 ms 364 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int MAXN = (int)(2e5)+5;

int dp[MAXN];
int main() {
    int N, M;
    cin >> N >> M;
    vector<pair<int, int>> F(N);
    vector<int> C(M);
    for (int i = 0; i < N; i++) {
        int f, s;
        cin >> f >> s;
        F[i] = {s, f};
    }
    for (int i = 0; i < M; i++) {
        cin >> C[i];
    }
    sort(F.rbegin(), F.rend());
    sort(C.rbegin(), C.rend());
    dp[0] = (F[0].second <= C[0]);
    int curMax = 0;
    for (int i = 1; i < N; i++) {
        int low = 0;
        int high = M-1;
        while (low < high) {
            int mid = (low + high+1)/2;
            if (C[mid] >= F[i].second) {
                low = mid;
            }
            else {
                high = mid-1;
            }
        }
        dp[i] = min(curMax+1, low+1);
        if (C[0] < F[i].second) {
            dp[i] = 0;
        }
        curMax = max(dp[i], curMax);
    }
    cout << curMax << '\n';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -