Submission #1013664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013664		Ludissey	Matryoshka (JOI16_matryoshka)	C++14	100 / 100	862 ms	101228 KiB

matryoshka

#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
 
using namespace std;

bool comp(pair<int,int> a, pair<int,int> b){
    if(a.second==b.second) return a.first<b.first;
    return a.second>b.second;
} 

bool comp2(pair<pair<int,int>,int> a, pair<pair<int,int>,int> b){
    if(a.first.second!=b.first.second) return a.first.second>b.first.second;
    return a.first.first>b.first.first;
} 

struct seg_tree{
    vector<int> bit;
    int n;
    seg_tree(int _n) {
        this->n = _n;
        bit.assign(_n, 0);
    }
    int mx(int r) {
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1) ret = max(ret,bit[r]);
        return ret;
    }

    void add(int idx, int val) {
        for (; idx < n; idx = idx | (idx + 1)) bit[idx] = max(bit[idx],val);
    }
};

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int N,Q; cin >> N >> Q;
    unordered_map<int,int> comprD;
    unordered_map<int,int> comprH;
    vector<pair<int,int>> a(N);
    set<int> d;
    set<int> h;
    for (int i = 0; i < N; i++)
    {
        cin >> a[i].first >> a[i].second;
        d.insert(a[i].second);
        h.insert(a[i].first);
    }
    vector<pair<pair<int,int>,int>> q(Q);
    for (int i = 0; i < Q; i++)
    {
        cin >> q[i].first.first >> q[i].first.second;
        d.insert(q[i].first.second);
        h.insert(q[i].first.first);
    }
    int cnt=0;
    for (auto u : d) { comprD[u]=cnt; cnt++; }
    int dN=cnt;
    cnt=0;
    for (auto u : h) { comprH[u]=cnt; cnt++; }
    dN=cnt;
    for (int i = 0; i < N; i++) a[i]={comprH[a[i].first],comprD[a[i].second]};
    for (int i = 0; i < Q; i++) q[i]={{comprH[q[i].first.first],comprD[q[i].first.second]},i};

    sort(all(a),comp);
    vector<int> lis(N); //pas strict decreasing de N-1 a 0
    int l=N-1;
    seg_tree fen(dN);
    for (int i = N-2; i >= 0; i--){
        if(a[i].second==a[i+1].second) continue;
        else{
            for (int j = l; j > i; j--)
            {
                int mx=fen.mx((dN-1)-a[j].first)+1;
                fen.add((dN-1)-a[j].first,mx);
                lis[j]=mx;
            }
            l=i;
        }
    }
    vector<pair<int,int>> to_add;
    for (int j = l; j >= 0; j--)
    {
        int mx=fen.mx((dN-1)-a[j].first)+1;
        fen.add((dN-1)-a[j].first,mx);
        lis[j]=mx;
    }
    //cerr << "\nLIS\n";
    for (int i = 0; i < N; i++)
    {
        //cerr << a[i].first << " " << a[i].second << " -> " << lis[i] << "\n";
    }
    //cerr<<"\n";

    sort(all(q),comp2);
    seg_tree fen2(dN);
    vector<int> ans(Q);
    int j=N-1;
    //for (int i = sz(q)-1; i >= 0; i--) cerr<<q[i].first.first<<" " << q[i].first.second <<" "<<q[i].second<< "\n";
    for (int i = sz(q)-1; i >= 0; i--)
    {

        while(j>=0&&a[j].second<=q[i].first.second){
            fen2.add((dN-1)-a[j].first,lis[j]);
            //cerr<<"add " << (dN-1)-a[j].first <<" with value of "<<lis[j]<< "\n";
            j--;
        }
        int mx=fen2.mx((dN-1)-q[i].first.first);
        ans[q[i].second]=mx;
    }
    for (int i = 0; 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