Submission #495922

#	Time	Username	Problem	Language	Result	Execution time	Memory
495922		Jarif_Rahman	Exhibition (JOI19_ho_t2)	C++17	100 / 100	108 ms	10608 KiB

joi2019_ho_t2

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
struct segtree{
    struct node{
        int in; ll mx;
        node(){
            mx = 0;
        }
        node(int _in, ll x){
            in = _in;
            mx = x;
        }
        node operator+(node a){
            return (a.mx >= mx ? node(a.in, a.mx):node(in, mx));
        }
    };
    int k;
    vector<node> v;
    segtree(int n){
        k = 1;
        while(k < n) k*=2;
        k*=2;
        v.resize(k);
        for(int i = k-1; i >= k/2; i--) v[i].in = i-k/2;
        for(int i = k/2-1; i > 0; i--) v[i] = v[2*i]+v[2*i+1];
    }
    void upd(int in, ll x){
        in+=k/2;
        v[in].mx = x;
        in/=2;
        while(in > 0){
            v[in] = v[2*in]+v[2*in+1];
            in/=2;
        }
    }
    pair<ll, int> smx(int l, int r, int nd, int a, int b){
        if(a > r || b < l) return {-1, -1};
        if(a >= l && b <= r) return {v[nd].mx, v[nd].in};
        int md = (a+b)/2;
        return max(smx(l, r, 2*nd, a, md), smx(l, r, 2*nd+1, md+1, b));
    }
    pair<ll, int> smx(int l, int r){
        return smx(l, r, 1, 0, k/2-1);
    }
};
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m; cin >> n >> m;
    
    vector<pair<ll, ll>> pics(n);
    vector<ll> frames(m), bs;

    for(auto &p: pics) cin >> p.f >> p.sc, bs.pb(-p.f);
    for(ll &x: frames) cin >> x;

    sort(pics.begin(), pics.end());
    sort(bs.begin(), bs.end());
    sort(frames.begin(), frames.end());

    segtree seg(n);
    for(int i = 0; i < n; i++) seg.upd(i, pics[i].sc);

    int ans = 0;
    for(int i = m-1; i >= 0; i--){
        auto it = lower_bound(bs.begin(), bs.end(), -frames[i]);
        int in = n-1-(it-bs.begin());
        if(in == -1) continue;
        auto p = seg.smx(0, in);
        if(p.f == 0) continue;
        ans++;
        seg.upd(p.sc, 0);
    }

    cout << ans << "\n";

}

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