Submission #1083915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083915		Icelast	Exhibition (JOI19_ho_t2)	C++17	0 / 100	0 ms	348 KiB

joi2019_ho_t2

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct SegmentTree{
    struct Node{
        ll mx = 0;
    };
    vector<Node> T;
    int n, N;
    SegmentTree(int n) : n(n){
        N = 1;
        while(N < n) N*=2;
        T.resize(N*2+1);
    };
    void upd(int i, ll x){
        auto upd = [&](auto upd, int node, int low, int high, int i, ll x) -> void{
            if(low == high){
                T[node].mx = max(T[node].mx, x);
                return;
            }
            int mid = (low+high)/2;
            if(i <= mid){
                upd(upd, node*2, low, mid, i, x);
            }else{
                upd(upd, node*2+1, mid+1, high, i, x);
            }
            T[node].mx = max(T[node*2].mx, T[node*2+1].mx);
        };
        upd(upd, 1, 1, N, i, x);
    }
    ll get_max(int l, int r){
        auto get_max = [&](auto get_max, int node, int low, int high, int l, int r) -> ll{
            if(low > r || l > high) return 0;
            if(low >= l && r >= high) return T[node].mx;
            int mid = (low+high)/2;
            return max(get_max(get_max, node*2, low, mid, l, r), get_max(get_max, node*2+1, mid+1, high, l, r));
        };
        return get_max(get_max, 1, 1, N, l, r);
    }
};
struct normalize{
    vector<ll> poi, pot;
    void add(ll x){
        poi.push_back(x);
    }
    void start(){
        sort(poi.begin(), poi.end());
        pot.push_back(poi[0]);
        for(int i = 1; i < (int)poi.size(); i++){
            if(poi[i] != poi[i-1]){
                pot.push_back(poi[i]);
            }
        }
    }
    int encode(ll x){
        return lower_bound(pot.begin(), pot.end(), x) - pot.begin()+1;
    }
};
struct point{
    ll x, y;
};
bool cmpxr(point a, point b){
    return a.x > b.x || (a.x == b.x && a.y > b.y);
}

void solve(){
    int n, m;
    cin >> n >> m;
    vector<point> a(n+1);
    vector<ll> b(m+1);
    for(int i = 1; i <= n; i++){
        cin >> a[i].x >> a[i].y;
    }
    for(int i = 1; i <= m; i++){
        cin >> b[i];
    }
    normalize norm;
    for(int i = 1; i <= n; i++){
        norm.add(a[i].x);
        norm.add(a[i].y);
        norm.add(b[i]);
    }
    norm.start();
    for(int i = 1; i <= n; i++){
        a[i].x = norm.encode(a[i].x);
        a[i].y = norm.encode(a[i].y);
    }
    for(int i = 1; i <= m; i++){
        b[i] = norm.encode(b[i]);
    }
    sort(b.begin()+1, b.end(), greater<ll>());
    b.push_back(-INF);
    sort(a.begin()+1, a.end(), cmpxr);
    vector<ll> dp(n+1, 0);
    int N = n+m+1;
    SegmentTree T(N+1);
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        ll mx = T.get_max(a[i].y, N)+1;
        ll j = upper_bound(b.begin()+1, b.end(), a[i].x) - b.begin()-1;
        if(j == m+1) j = 0;
        mx = min(mx, j);
        dp[i] = mx;
        T.upd(a[i].y, dp[i]);
        ans = max(ans, dp[i]);
    }
    cout << ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

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