oj.uz

Submission #881630

# Submission time Handle Problem Language Result Execution time Memory
881630 2023-12-01T16:06:12 Z JakobZorz Exhibition (JOI19_ho_t2) C++14
0 / 100
 0 ms 348 KB 
#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=n;
        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==n)
            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
0 / 10.0

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

Subtask #2
0 / 40.0

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

Subtask #3
0 / 50.0

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