Submission #901898

#	Time	Username	Problem	Language	Result	Execution time	Memory
901898		ForgottenDestiny	Exhibition (JOI19_ho_t2)	C++17	50 / 100	1050 ms	11484 KiB

joi2019_ho_t2

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

int n;
vector<int> seg;

void build() {
    for(int i=n-1;i>0;i--) seg[i]=max(seg[i<<1],seg[i<<1|1]);
}


void modify(int p, int value) {
    for(seg[p+=n]=value;p>1;p>>=1) seg[p>>1]=max(seg[p],seg[p^1]); 
}

int query(int l, int r){ // remember, this works over range [l,r)
    int res=-1;
    for(l+=n,r+=n;l<r;l>>=1,r>>=1){
        if(l&1) res=max(res,seg[l++]); //remember, this needs to be l++, ++l will WA
        if(r&1) res=max(res,seg[--r]); 
    }
    return res;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m;
    cin>>n>>m;
    vector<pair<int,int>> pics(n);
    seg.resize(2*n);
    vector<int> frames(m);
    for (int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        pics[i]={a,b};
    }
    sort(pics.begin(),pics.end());
    for(int i=0;i<m;i++){
        cin>>frames[i];
    }
    sort(frames.begin(),frames.end());
    set<tuple<int,int,int>> values;
    for (int i=0;i<n;i++){
        values.insert({pics[i].second,pics[i].first,i});
    }
    for (int i=0;i<n;i++){
        seg[n+i]=pics[i].second;
    }
    build();
    int res=0;
    for(int i=m-1;i>=0;i--){
        auto it=upper_bound(pics.begin(),pics.end(),make_pair(frames[i],(int)1e9+1));
        if(it==pics.begin()){
            break;
        }
        int r=it-pics.begin();
        // cerr<<r<<"\n";
        int k = query(0,r);
        // cerr<<k<<"\n";
        if(k==-1){
            break;
        }
        res++;
        tuple<int,int,int> cur={k,frames[i],n+1};
        auto it2=upper_bound(values.begin(),values.end(),cur);
        it2--;
        int sec=get<2>(*it2);
        modify(sec,-1);
        values.erase(it2);

    }
    cout<<res<<"\n";

    return 0;
}

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