Submission #341347

#	Time	Username	Problem	Language	Result	Execution time	Memory
341347		bigDuck	Exhibition (JOI19_ho_t2)	C++14	100 / 100	262 ms	24684 KiB

joi2019_ho_t2

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll

int t, n, m, s[100010], v[100010], c[100010];
pii pr[100010];
map<pii, vector<int>> h;
bool pos[100010];

multiset<pii> ms;


int32_t main(){
INIT
cin>>n>>m;

for(int i=1; i<=n; i++){
    cin>>s[i]>>v[i];
    ms.insert({v[i], s[i]});
    pr[i]={s[i], v[i]};
}
sort(pr+1 , pr+1+n);

for(int i=1; i<=n; i++){
    pos[i]=true;
    h[pr[i] ].pb(i);
}

for(int i=1; i<=m ;i++){
    cin>>c[i];
}
sort(c+1, c+1+m);

int pt=n;
int res=0;

for(int i=m; i>=1; i--){

    while( (pt>=1) && ( (pos[pt]==false) || (pr[pt].ft>c[i]) ) ){
        if(pos[pt]==false){
            pt--; continue;
        }
        ms.erase(ms.find({pr[pt].sc, pr[pt].ft}) );
        pt--;
    }

    if(pt>=1){
        res++;
        auto it=ms.end();
        it--;
        int loc=(h[ make_pair(it->sc, it->ft) ].back() ); h[ make_pair(it->sc, it->ft) ].pop_back(); pos[loc]=false;
        ms.erase(it);
    }
    else{
        break;
    }

}
cout<<res;


return 0;
}

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