Submission #1308722

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308722		_nothing_	Exhibition (JOI19_ho_t2)	C++17	0 / 100	1 ms	572 KiB

joi2019_ho_t2

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

struct Data {
    int Size, val;

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

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: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 50