Submission #913655

#	Time	Username	Problem	Language	Result	Execution time	Memory
913655		SadraMzf	Exhibition (JOI19_ho_t2)	C++17	0 / 100	1 ms	2396 KiB

joi2019_ho_t2

#include <bits/stdc++.h>
using namespace std;
 
#define pt "--> "
#define Fast() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
typedef long long int ll ;
const int N = 2e5 + 7 , lg = 27 , len = 340 , Sq = 350 , oo = 2e9 , mod = 998244353 ;
int dx[9] = {0 , -1 , 0 , 1 , 0 , 1 , 1 , -1 , -1} , dy[9] = {0 , 0 , -1 , 0 , 1 , 1 , -1 , 1 , -1} ;

int n , m ;
int a[N] , val[N] , dp[N] ;
vector<int> vec ;
pair<int,int> p[N] ;
set<int> st ;

void solve() {
    cin >> n >> m ;
    for(int i = 1 ; i <= n ; i++)
        cin >> p[i].second >> p[i].first ;
    for(int i = 1 ; i <= m ; i++) {
        int x ; cin >> x ;
        st.insert(x) ;
    }
    sort(p+1 , p+1+n) ;
    for(int i = 1 ; i <= n ; i++)
        a[i] = p[i].second ;
    
    for(int i = 1 ; i <= n ; i++) {
        if(st.lower_bound(a[i]) == st.end())
            val[i] = -1 ;
        else {
            val[i] = *st.lower_bound(a[i]) ;
            st.erase(st.lower_bound(a[i])) ;
        }
    }

    vec.push_back(-1) ;
    for(int i = 1 ; i <= n ; i++)
        if(val[i] != -1)
            vec.push_back(val[i]) ;
    
    if(vec.size() == 1) {
        cout << 0 << endl ;
        return ;
    }

    fill(dp , dp+N , oo) ;
    dp[0] = -oo ;
    for(int i = 1 ; i <= n ; i++)
        *lower_bound(dp , dp+i+1 , vec[i]) = vec[i] ;
    cout << lower_bound(dp , dp+N , oo) - dp - 1 << endl ;
}

int main(){
	// Fast() ;

    int T = 1 ;
    while(T--)
        solve() ;
}

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