제출 #484119

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
484119		ponytail	Exhibition (JOI19_ho_t2)	C++17	100 / 100	173 ms	9740 KiB

joi2019_ho_t2

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

#define int long long

const int MAXN = 1e5 + 10;
pair<int, int> a[4*MAXN];

void update(int l, int r, int tar, int idx, int val) {
    if(l == r) {
        a[idx] = {val, tar};
        return;
    }
    int mid = (l+r) / 2;
    if(tar <= mid) update(l, mid, tar, 2*idx+1, val);
    else update(mid+1, r, tar, 2*idx+2, val);
    a[idx] = max(a[2*idx+1], a[2*idx+2]);
}
pair<int, int> query(int l, int r, int constl, int constr, int idx) {
    if(l <= constl && constr <= r) return a[idx];
    int mid = (constl + constr) / 2;
    if(mid < l || r < constl) return query(l, r, mid+1, constr, 2*idx+2);
    else if(constr < l || r < mid+1) return query(l, r, constl, mid, 2*idx+1);
    else return max(query(l, r, constl, mid, 2*idx+1), query(l, r, mid+1, constr, 2*idx+2));
}

signed main() {
    int N, M; cin >> N >> M;
    pair<int, int> p[N+1]; for(int i=1; i<=N; i++) cin >> p[i].first >> p[i].second;
    int c[M+1]; for(int i=1; i<=M; i++) cin >> c[i];
    sort(p+1, p+N+1);
    sort(c+1, c+M+1);
    for(int i=1; i<=N; i++) update(1, N, i, 0, p[i].second);
    vector<int> v;
    for(int i=M; i>=1; i--) {
        int lb = 1, rb = N;
        while(lb < rb) {
            int mid = (lb+rb+1) / 2;
            if(p[mid].first <= c[i]) lb = mid;
            else rb = mid-1;
        }
        if(p[lb].first <= c[i]) {
            pair<int, int> res = query(1, lb, 1, N, 0);
            if(v.size() && res.first > v.back()) return cout << M-i << '\n', 0;
            if(res.first == 0) return cout << M-i << '\n', 0;
            update(1, N, res.second, 0, 0);
        }
        else {
            return cout << M-i << '\n', 0;
        }
    }
    cout << M << '\n';
}

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