Submission #1189303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189303		Born_To_Laugh	Matryoshka (JOI16_matryoshka)	C++17	100 / 100	200 ms	16912 KiB

matryoshka

// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(sth) sth.begin(), sth.end()
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 1e9 + 7;
#define int ll
class Fenwick_Tree
{
  private:
    int n;
    vector<int> bit;
  public:
    Fenwick_Tree(int len){
        n = len;
        bit.assign(n+1, 0);
    }
    void Point_Update(int pos, int val){
        for(; pos<=n; pos += pos&(-pos)){
            bit[pos] = max(bit[pos], val);
        }
    }
    int get_max(int pos){
        int ans = 0;
        for(; pos>0; pos -= pos&(-pos)){
            ans = max(ans, bit[pos]);
        }
        return ans;
    }
};
void solve(){
    int n, q;cin >> n >> q;
    vector<pair<int,int>> item(n+1);
    for(int i=1; i<=n; ++i){
        cin >> item[i].first >> item[i].second;
    }
    sort(item.begin() + 1, item.end(), [](pair<int,int> a, pair<int,int> b){
        if(a.first != b.first)return a.first > b.first;
        return a.second < b.second;
    });

    vector<array<int,3>> query(q+1);
    for(int i=1; i<=q; ++i){
        cin >> query[i][0] >> query[i][1];
        query[i][2] = i;
    }
    sort(query.begin() + 1, query.end(), [](array<int, 3> a, array<int, 3> b){
        if(a[0] != b[0])return a[0] > b[0];
        return a[1] < b[1];
    });

    vector<int> compress;
    for(int i=1; i<=n; ++i){
        compress.push_back(item[i].second);
    }
    for(int i=1; i<=q; ++i){
        compress.push_back(query[i][1]);
    }
    sort(alle(compress));
    compress.erase(unique(alle(compress)), compress.end());
    auto get_pos = [&](int val){
        int pos = lower_bound(alle(compress), val) - compress.begin();
        return pos + 1;
    };

    Fenwick_Tree ft(compress.size() + 10);
    vector<int> ans(q+1, 0);
    int j = 1;
    for(int i=1; i<=q; ++i){
        while(j <= n && item[j].first >= query[i][0]){
            ft.Point_Update(get_pos(item[j].second), ft.get_max(get_pos(item[j].second)) + 1);
            j++;
        }
        ans[query[i][2]] = ft.get_max(get_pos(query[i][1]));
    }
    for(int i=1; i<=q; ++i){
        cout << ans[i] << '\n';
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

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