제출 #881635

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
881635		JakobZorz	Exhibition (JOI19_ho_t2)	C++14	100 / 100	54 ms	5320 KiB

joi2019_ho_t2

#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
#include<cstring>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
//const int MOD=1e9+7;
//typedef pair<ll,ll>Point;
//typedef pair<ll,ll>Line;
//#define x first
//#define y second
 
void solve(){
    int n,m;
    cin>>n>>m;
    vector<int>frames(m);
    vector<pair<int,int>>pictures_pairs(n);
    vector<int>pictures(n);
    for(auto&i:pictures_pairs)
        cin>>i.second>>i.first;
    for(int&i:frames)
        cin>>i;
    sort(pictures_pairs.begin(),pictures_pairs.end());
    sort(frames.begin(),frames.end());
    for(int i=0;i<n;i++)
        pictures[i]=pictures_pairs[i].second;
    vector<int>dp(n+1); // if you use picture i and all after, whats the max you can put inside?
    for(int i=n-1;i>=0;i--){
        int l=-1,r=m+1;
        while(l<r-1){
            int mid=(l+r)/2;
            if(frames[mid]>=pictures[i])
                r=mid;
            else
                l=mid;
        }
        // r is good, l is bad, if l = -1, then none is bad, if r = n, then none is good
        if(r==m)
            continue;
        
        dp[i]=min(dp[i+1],m-r-1)+1;
        dp[i]=max(dp[i],dp[i+1]);
    }
    
    cout<<dp[0]<<"\n";
}

int main(){
    ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
    //freopen("bank.in","r",stdin);freopen("bank.out","w",stdout);
    int t=1;//cin>>t;
    while(t--)solve();
    return 0;
}

/*
 
3 4
10 20
5 1
3 5
4
6
10
4
 
2
 

3 2
1 2
1 2
1 2
1
1

2
 
 
4 2
28 1
8 8
6 10
16 9
4
3
 
0
 
8 8
508917604 35617051
501958939 840246141
485338402 32896484
957730250 357542366
904165504 137209882
684085683 775621730
552953629 20004459
125090903 607302990
433255278
979756183
28423637
856448848
276518245
314201319
666094038
149542543

3
 
 */

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