제출 #1308737

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308737		_nothing_	Exhibition (JOI19_ho_t2)	C++17	100 / 100	71 ms	2408 KiB

joi2019_ho_t2

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

struct Data {
    int Size, val;

    bool operator < (const Data &other) const {
        if (val != other.val) return val < other.val;
        return Size < other.Size;
    }
};

int numPic, numFrame;

#define MAX_N 100100
Data a[MAX_N];
int frame[MAX_N];

struct Fenwick {
    int bit[MAX_N];

    void update(int x, int v) {
        for (; x <= numPic; x += x & (-x)) bit[x] = max(bit[x], v);
    }

    int get(int x) {
        int ans = 0;
        for (; x > 0; x -= x & (-x)) ans = max(ans, bit[x]);
        return ans;
    }
} maxTree;

bool check(int val) {
    for (int i = 1; i <= numPic; ++i) maxTree.bit[i] = 0; // reset;

    for (int i = 1; i <= numPic; ++i) {
        int cur = maxTree.get(a[i].val);

        if (cur == val) return true;
        assert(numFrame - val + cur + 1 <= numFrame);
        if (frame[numFrame - val + cur + 1] >= a[i].Size) {
            maxTree.update(a[i].val, cur + 1);
            if (cur + 1 == val) return true;
        }
    }

    return false;
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    cin >> numPic >> numFrame;
    for (int i = 1; i <= numPic; ++i) cin >> a[i].Size >> a[i].val;
    for (int i = 1; i <= numFrame; ++i) cin >> frame[i];

    sort(a + 1, a + 1 + numPic);
    sort(frame + 1, frame + 1 + numFrame);

    vector<int> compressed;
    for (int i = 1; i <= numPic; ++i) compressed.push_back(a[i].val);

    sort(compressed.begin(), compressed.end());
    compressed.resize(unique(compressed.begin(), compressed.end()) - compressed.begin());

    for (int i = 1; i <= numPic; ++i) a[i].val = upper_bound(compressed.begin(), compressed.end(), a[i].val) - compressed.begin();

    int l = 1, r = min(numPic, numFrame), g, vt = 0;
    while (l <= r) {
        g = (l + r) >> 1;
        if (check(g)) vt = g, l = g + 1;
        else r = g - 1;
    }

    cout << vt;

    return 0;
}

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