Submission #1267367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267367		dhuyyyy	Matryoshka (JOI16_matryoshka)	C++20	100 / 100	104 ms	14252 KiB

matryoshka

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

using ll = long long;
using ii = pair<int,int>;
using pii = pair<int,ii>;
using aa = array<int,3>;

const int N = 2e5+5;
const int INF = 1e9;
const int MOD = 1e9+21;

int n, m, q;

int ans[N];

ii doll[N];

aa query[N];

vector <ii> dp;

/*
minimum increasing sequences of an array

==

longest non-increasing sequence of that array
*/
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> q;
    for (int i = 1; i <= n; i++){
        cin >> doll[i].fi >> doll[i].se;
        doll[i].se = -doll[i].se; //avoid h[i] > h[j] but r[i] == r[j] when cnp
    }
    sort(doll+1,doll+1+n,greater<ii>());
    for (int i = 1; i <= q; i++){
        cin >> query[i][0] >> query[i][1];
        query[i][2] = i;
    }
    sort(query+1,query+1+q,greater<aa>());
    int j = 1;
    for (int i = 1; i <= q; i++){
        while (j <= n && doll[j].fi >= query[i][0]){
            int LNIS = upper_bound(dp.begin(),dp.end(),make_pair(-doll[j].se,INF)) - dp.begin();
            if (LNIS == (int)dp.size()) dp.push_back({-doll[j].se,doll[j].fi});
            else dp[LNIS] = {-doll[j].se,doll[j].fi};
            j++;
        }
        ans[query[i][2]] = upper_bound(dp.begin(),dp.end(),make_pair(query[i][1],INF)) - dp.begin();
    }
    for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 49 / 49