oj.uz

Submission #913655

# Submission time Handle Problem Language Result Execution time Memory
913655 2024-01-20T08:39:05 Z SadraMzf Exhibition (JOI19_ho_t2) C++17
0 / 100
 1 ms 2396 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Halted 0 ms 0 KB -