제출 #238395

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
238395		haengsyo	Exhibition (JOI19_ho_t2)	C++14	50 / 100	1082 ms	8624 KiB

joi2019_ho_t2

#pragma GCC optimize("O3")

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
tree<int,int,greater<int>,rb_tree_tag,tree_order_statistics_node_update> map_t;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for(int i = 0; i < (a); ++i)
#define sz(x) (int)x.size()
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define REV(x) reverse(x.begin(),x.end())
int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};
int n,m;
const int mxN=1e5+5;
const int INF=2e9;
pair<int,int> arr[mxN];
int sizes[mxN];

int t[4*mxN],p[4*mxN];

void recalc(int v) {
    if(t[2*v]<t[2*v+1]) {
        t[v]=t[2*v];
        p[v]=p[2*v];
    }
    else {
        t[v]=t[2*v+1];
        p[v]=p[2*v+1];
    }
}

void build(int v,int tl,int tr) {
    if(tl==tr) {
        t[v]=arr[tl].second;
        p[v]=tl;
        return;
    }
    int mid=tl+(tr-tl)/2;
    build(2*v,tl,mid);
    build(2*v+1,mid+1,tr);
    recalc(v);
}

pair<int,int> qry(int v,int tl,int tr,int l,int r) {
    if(tr<l || tl>r)
        return {-1,INF};
    if(tl>=l && tr<=r)
        return {p[v],t[v]};
    int mid=tl+(tr-tl)/2;
    pair<int,int> left=qry(2*v,tl,mid,l,r);
    pair<int,int> right=qry(2*v+1,mid+1,tr,l,r);
    if(left.second<right.second)
        return left;
    return right;
}

void upd(int v,int tl,int tr,int pos,int val) {
    if(tr<pos || tl>pos)
        return;
    if(tl==tr) {
        t[v]=val;
        p[v]=pos;
        return;
    }
    int mid=tl+(tr-tl)/2;
    upd(2*v,tl,mid,pos,val);
    upd(2*v+1,mid+1,tr,pos,val);
    recalc(v);
}

int binSearch2(int val) {
    int l,h;
    l=0; h=n-1;
    int res=-1;
    while(l<=h) {
        int mid=l+(h-l)/2;
        if(arr[mid].first<=val) {
            res=mid;
            l=mid+1;
        }
        else
            h=mid-1;
    }
    return res;
}

bool check(int val) {
    vector<pair<int,int>> rem;
    int prev=-1;
    bool res=true;
    FOR(i,m-val,m) {
        int pos=binSearch2(sizes[i]);
        if(pos==-1) {
            res=false;
            goto end;
        }
        pair<int,int> mn={-1,-1};
        while(true) {
            mn=qry(1,0,n-1,0,pos);
            if(mn.second==INF) {
                res=false;
                goto end;
            }
            rem.push_back(mn);
            upd(1,0,n-1,mn.first,INF);
            if(mn.second>=prev)
                break;
        }
        prev=mn.second;
    }
    end:;
    for(auto p : rem)
        upd(1,0,n-1,p.first,p.second);
    return res;
}

int binSearch() {
    int l,h;
    l=0; h=min(m,n);
    int res=0;
    while(l<=h) {
        int mid=l+(h-l)/2;
        if(check(mid)) {
            res=mid;
            l=mid+1;
        }
        else
            h=mid-1;
    }
    return res;
}

int main() {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;
    F0R(i,n)
        cin >> arr[i].first >> arr[i].second;
    F0R(i,m)
        cin >> sizes[i];
    sort(arr,arr+n);
    sort(sizes,sizes+m);
    build(1,0,n-1);
    cout << binSearch();

    return 0;
}

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