Submission #1360936

#TimeUsernameProblemLanguageResultExecution timeMemory
1360936waygonzExhibition (JOI19_ho_t2)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>
#define f first
#define s second

using namespace std;

struct FenwickTree {
    int N;
    vector<int> fw, a;
    void update(int x, int v) {
        int u = a[x];
        while (x <= N) fw[x] += v - u, x += x & -x;
        a[x] = v;
    }
    int query(int x) {
        int res = 0;
        while (x > 0) res += fw[x], x -= x & -x;
        return res;
    }
} T;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> a(n+1), b(m+1);
    for (int i = 1; i <= n; i++) cin >> a[i].s >> a[i].f;
    for (int i = 1; i <= m; i++) cin >> b[i].f, b[i].s = INT_MAX;
    sort(a.begin() + 1, a.end());
    sort(b.begin() + 1, b.end());
    T.N = m;
    T.fw.assign(m+1, 0);
    T.a.assign(m+1, 0);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (b.back().f < a[i].s || b.back().f == a[i].s && b.back().s <= a[i].s) continue;
        int id = upper_bound(b.begin() + 1, b.end(), make_pair(a[i].s, a[i].s)) - b.begin();
        int t = T.query(id-1) + 1;
        if (t > ans) T.update(id, 1), ans = t;
        b[id] = {a[i].s, a[i].s};
    }
    cout << ans;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...