Submission #545052

#	Time	Username	Problem	Language	Result	Execution time	Memory
545052		pokmui9909	Matryoshka (JOI16_matryoshka)	C++17	100 / 100	538 ms	51404 KiB

matryoshka

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Data{
    ll x, y, n;
    bool operator < (const Data &r) const{
        if(x != r.x) return x > r.x;
        else return y < r.y;
    }
};
Data Query[200005];
ll ans[200005];
const ll S = 400005;
ll len[200005];

struct MaxSeg{
    ll T[4 * S] = {};
    void update(ll k, ll v) { update(1, 1, S, k, v); }
    ll query(ll l, ll r) { return query(1, 1, S, l, r); }

    void update(ll node, ll s, ll e, ll k, ll v){
        if(s == e){
            T[node] = max(T[node], v);
            return;
        }
        ll lch = 2 * node, rch = 2 * node + 1, m = (s + e) / 2;
        if(k <= m) update(lch, s, m, k, v);
        else update(rch, m + 1, e, k, v);
        T[node] = max(T[lch], T[rch]);
    }
    ll query(ll node, ll s, ll e, ll l, ll r){
        if(e < l || s > r) return 0;
        if(l <= s && e <= r) return T[node];
        ll lch = 2 * node, rch = 2 * node + 1, m = (s + e) / 2;
        ll x = query(lch, s, m, l, r);
        ll y = query(rch, m + 1, e, l, r);
        return max(x, y);
    }
};

int main(){
    cin.tie(0) -> sync_with_stdio(false);

    ll N, Q; cin >> N >> Q;
    vector<pair<ll, ll>> P(N);
    vector<ll> X, Y;
    for(int i = 0; i < N; i++){
        cin >> P[i].first >> P[i].second;
        X.push_back(P[i].first);
        Y.push_back(P[i].second);
    }
    sort(P.begin(), P.end(), [&](pair<ll, ll> a, pair<ll, ll> b) -> bool{
        if(a.first != b.first) return a.first > b.first;
        else return a.second < b.second;
    });
    for(int i = 0; i < Q; i++){
        cin >> Query[i].x >> Query[i].y;
        Query[i].n = i;
        X.push_back(Query[i].x);
        Y.push_back(Query[i].y);
    }
    sort(Query, Query + Q);
    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());
    X.erase(unique(X.begin(), X.end()), X.end());
    Y.erase(unique(Y.begin(), Y.end()), Y.end());
    for(int i = 0; i < N; i++){
        P[i].first = lower_bound(X.begin(), X.end(), P[i].first) - X.begin() + 1;
        P[i].second = lower_bound(Y.begin(), Y.end(), P[i].second) - Y.begin() + 1;
    }
    for(int i = 0; i < Q; i++){
        Query[i].x = lower_bound(X.begin(), X.end(), Query[i].x) - X.begin() + 1;
        Query[i].y = lower_bound(Y.begin(), Y.end(), Query[i].y) - Y.begin() + 1;
    }
    MaxSeg LIS;
    for(int i = 0; i < N; i++){
        len[i] = LIS.query(1, P[i].second) + 1;
        LIS.update(P[i].second, len[i]);
    }
    ll idx = -1;
    MaxSeg ST;
    for(int i = 0; i < Q; i++){
        while(1){
            idx++;
            if(P[idx].first < Query[i].x || idx >= N){
                idx--;
                break;
            }
            ST.update(P[idx].second, len[idx]);
        }
        ans[Query[i].n] = ST.query(1, Query[i].y);
    } 
    for(int i = 0; i < Q; i++){
        cout << ans[i] << '\n';
    }
}

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