Submission #1283334

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283334		zagaro	Exhibition (JOI19_ho_t2)	C++20	0 / 100	1 ms	572 KiB

joi2019_ho_t2

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
/**zagaro & lauren <3**/
#define mod 1000000007 //1e9 + 7
#define pi acos(-1)
#define wl while
#define str string
#define ENDL "\n"
#define sal ' '
#define tp_set ll
#define prc(n) cout.precision(n);cout<<fixed;
#define ord_set tree<tp_set, null_type, less<tp_set>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef bool bl;
typedef char car;
using namespace std;
using namespace __gnu_pbds;
vector<ll> tr;
vector<ll> frm;
void build(ll ind, ll l, ll r){
    if(l == r){tr[ind] = frm[l];return ;}
    build(ind*2, l, (l+r)/2);
    build(ind*2+1, (l+r)/2+1, r);
    tr[ind] = max(tr[ind*2], tr[ind*2+1]);
    return ;
}
ll query(ll ind, ll l, ll r, ll x, ll y, ll v){
    if(y < l || r < x)return LONG_LONG_MAX;
    if(tr[ind] < v)return LONG_LONG_MAX;
    if(l == r && tr[ind] >= v)return l;
    ll a;
    a = query(ind*2, l, (l+r)/2, x, y, v);
    if(a != LONG_LONG_MAX)return a;
    else return query(ind*2+1, (l+r)/2+1, r, x, y, v);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, m, l, r, M, x;
    cin>>n>>m;
    vector<pair<ll,ll> > vec(n+1);
    frm.assign(m+1, 0);
    tr.assign(3*m+10, 0);
    vector<ll> dp(1, 0);
    vector<ll> ps(1, 0);
    for(int i=1;i<=n;i++)cin>>vec[i].first>>vec[i].second;
    sort(vec.begin(), vec.end());
    for(int i=1;i<=m;i++)cin>>frm[i];
    sort(frm.begin(), frm.end());
    build(1, 1, m);
    for(int i=1;i<=n;i++){
        l=0;r=dp.size();
        wl(l<r-1){
            M = (l+r)/2;
            if(dp[M] <= vec[i].second)l=M;
            else r=M;
        }
        x = query(1, 1, m, ps[l]+1, m, vec[i].first);
        if(x != LONG_LONG_MAX){
            if(l == dp.size()-1){
                dp.push_back(vec[i].second);
                ps.push_back(x);
            }
            else {
                dp[r] = vec[i].second;
                ps[r] = x;
            }
        }
    }
    cout<<dp.size()-1<<ENDL;
    return 0;
}

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