Submission #1305212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305212		polishprogrammer	Exhibition (JOI19_ho_t2)	C++20	0 / 100	1 ms	572 KiB

joi2019_ho_t2

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
int wie;

int tree_size(int n) {
    int wynik = 1;
    while (wynik < n) wynik *= 2;
    return wynik * 2;
}
void update(vector<int>& tree, int i, int x) {
    i += wie / 2;
    tree[i] = x;
    while (i > 1) {
        i /= 2;
        tree[i] = max(tree[2 * i], tree[2 * i + 1]);
    }
}
int query(vector<int>& tree, int l, int r) {
    if (l > r) return 0;
    l += wie / 2;
    r += wie / 2;
    int res = 0;
    while (l <= r) {
        if (l % 2 == 1) res = max(res, tree[l++]);
        if (r % 2 == 0) res = max(res, tree[r--]);
        l /= 2;
        r /= 2;
    }
    return res;
}
void ctree(vector<int>& tree) {
    cout << "drzewo" << endl;
    for (int poz = 0; (1 << (poz + 1)) <= wie; poz++) {
        for (int j = (1 << poz); j < (1 << (poz + 1)); j++) {
            cout << tree[j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, x;
    cin >> n >> m;
    wie = tree_size(m);
    vector<int> dp(wie, 0);
    vector<pair<int, int>> obr(n);
    multiset<int> roz;
    for (int i = 0; i < n; i++) cin >> obr[i].se >> obr[i].fi;
    for (int i = 0; i < m; i++) {
        cin >> x;
        roz.insert(x);
    }
    auto it = roz.begin();
    unordered_map<int, deque<int>> mapa;
    for (int i = 0; i < m; i++) {
        mapa[*it].push_front(i);
        it++;
    }

    sort(obr.begin(), obr.end());
    for (pair<int, int> p : obr) {
        auto it = roz.lower_bound(p.se);
        if (it == roz.end()) continue;
        update(dp, mapa[*it].back(), query(dp, 0, mapa[*it].back() - 1) + 1);
        mapa[*it].pop_back();
        roz.erase(it);
    }
    cout << query(dp, 0, m - 1);
}

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