Submission #1136266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136266		byunjaewoo	조화행렬 (KOI18_matrix)	C++20	100 / 100	1298 ms	270640 KiB

matrix

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

const int N=200010, S=(1<<18);
int m, n, ans, d[N];
pair<pair<int, int>, int> a[N];
pair<int, int> b[N];
vector<int> v;

class Seg {
public:
    void Update(int k, int x, int v) {Update(1, 1, S, k, x, v);}
    int Query(int k, int x) {return Query(1, 1, S, 1, k, x);}
private:
    set<pair<int, int>> tree[2*S];
    void Update(int node, int s, int e, int k, int x, int v) {
        auto q=tree[node].lower_bound({x, v});
        if(q!=tree[node].begin() && (*prev(q)).second>=v);
        else {
            tree[node].insert({x, v});
            while(true) {
                auto p=tree[node].upper_bound({x, v});
                if(p!=tree[node].end() && (*p).second<=v) tree[node].erase(p);
                else break;
            }
        }
        if(s==e) return;
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        if(k<=m) Update(lch, s, m, k, x, v);
        else Update(rch, m+1, e, k, x, v);
    }
    int Query(int node, int s, int e, int l, int r, int x) {
        if(s>r || l>e) return 0;
        if(l<=s && e<=r) {
            auto p=tree[node].upper_bound({x, LLONG_MAX});
            if(p==tree[node].begin()) return 0;
            return (*prev(p)).second;
        }
        int lch=2*node, rch=lch+1, m=(s+e)/2;
        return max(Query(lch, s, m, l, r, x), Query(rch, m+1, e, l, r, x));
    }
}T;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>m>>n;
    if(m==2) {
        for(int i=1; i<=n; i++) cin>>b[i].first;
        for(int i=1; i<=n; i++) cin>>b[i].second;
        sort(b+1, b+n+1);
        vector<int> v;
        for(int i=1; i<=n; i++) {
            auto p=lower_bound(v.begin(), v.end(), b[i].second);
            if(p==v.end()) v.push_back(b[i].second);
            else (*p)=b[i].second;
        }
        cout<<v.size();
        return 0;
    }
    for(int i=1; i<=n; i++) cin>>a[i].first.first;
    for(int i=1; i<=n; i++) cin>>a[i].first.second;
    for(int i=1; i<=n; i++) cin>>a[i].second;
    for(int i=1; i<=n; i++) v.push_back(a[i].first.second);
    sort(v.begin(), v.end());
    for(int i=1; i<=n; i++) a[i].first.second=lower_bound(v.begin(), v.end(), a[i].first.second)-v.begin()+1;
    sort(a+1, a+n+1);
    for(int i=1; i<=n; i++) {
        d[i]=T.Query(a[i].first.second, a[i].second)+1;
        T.Update(a[i].first.second, a[i].second, d[i]);
        ans=max(ans, d[i]);
    }
    cout<<ans;
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 9 / 9
• Subtask 3: 15 / 15
• Subtask 4: 62 / 62