Submission #1122280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122280		Ryu	Exhibition (JOI19_ho_t2)	C++17	0 / 100	1 ms	460 KiB

joi2019_ho_t2

#include <bits/stdc++.h>
#define sts(v) stable_sort(v.BE, v.E)
#define Rsts(v) stable_sort(v.rBE, v.rE)
#define rev(v) reverse(v.BE, v.E)
#define BE begin()
#define rBE rbegin()
#define E end()
#define rE rend()
#define pb push_back
#define ppb pop_back()
#define pf push_front
#define ppf pop_front()
#define F first
#define S second
    
using namespace std;
using ll = long long;
using T = pair<ll, ll>;
const int M = 998244353;

struct ABI{
    vector<pair<int, int>> abi;
    ABI(int n){
        abi.resize(n + 1);
    }
    void updt(int ini, int val){
        for(int i = ini; i < (int)abi.size(); i += i & -i){
            if(abi[i].F < val)
                abi[i] = {val, ini};
            else if(abi[i].F == val)
                abi[i].S = min(ini, abi[i].S);
        }
            
    }
    pair<int, int> query(int i){
        pair<int, int> ans = {0, 0};
        for(; i > 0; i -= i & -i)
            if(ans.F < abi[i].F)
                ans = abi[i];
        return ans;
    }
};

int bs(vector<int> &v, int val) {
    int l = 1, r = v.size() - 1, ans = -1;

    while(l < r) {
        int m = (l + r) / 2;

        if(v[m] <= val) l = m + 1, ans = m;
        else r = m - 1;
    }
    return ans;
}

int main(){
    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    
    // st para guardar la respuesta en la caja i
    // dp[i] = query(1, n - 1)

    int n, m; cin >> n >> m;
    vector<pair<int, int>> v(n + 1, {INT_MIN, INT_MIN});
    vector<int> F(m + 1, INT_MIN);
    for(int i = 1; i <= n; i++){
        int w, val; cin >> w >> val;

        v[i] = {val, w};
    }
    for(int i = 1; i <= m; i++)
        cin >> F[i];

    sts(F);
    sts(v);
    

    int res = 0;
    ABI abi(m);

    for(int i = 1; i <= n; i++){
        int k = lower_bound(F.BE, F.E, v[i].S) - F.BE;
        
        if(k == m + 1)continue;

        pair<int, int> ans = abi.query(m - 1);

        if(!ans.F)ans = {1, k};
        else{
            ans.F++;
            if(k > ans.S)ans.S = k;
            else ans.S++;
        }
        
        abi.updt(ans.S, ans.F);
        //val, pos
        res = max(res, ans.F);
    }

    cout << res;

    return 0;
}

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