Submission #69083

#	Time	Username	Problem	Language	Result	Execution time	Memory
69083		Diuven	조화행렬 (KOI18_matrix)	C++14	100 / 100	730 ms	235816 KiB

matrix

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=200010, inf=2e9;

int m, n;
struct pt2{
    int x, y;
    bool operator < (const pt2 & p) const {
        return x<p.x || (x==p.x && y<p.y);
    }
};

struct pt3{
    int x, y, z;
} P[MX];

struct stair_st {
    set<pt2> S;
    void init(){
        S.insert({0,inf});
        S.insert({inf,0});
    }
    void put(pt2 &p){
        auto rit=S.upper_bound(p);
        if(prev(rit)->y < p.y) return;
        while(rit->y >= p.y) S.erase(rit++);
        S.insert(p);
    }
    bool valid(pt2 &p){
        auto rit=S.upper_bound(p); rit--;
        if(rit->y <= p.y) return true;
        return false;
    }
} Stair[MX];

void solve3(){

    vector<int> X;
    for(int i=1; i<=n; i++) X.push_back(P[i].x);
    sort(X.begin(), X.end());
    X.resize(unique(X.begin(), X.end())-X.begin());
    for(int i=1; i<=n; i++) P[i].x=lower_bound(X.begin(), X.end(), P[i].x)-X.begin()+1;

    vector<int> Y;
    for(int i=1; i<=n; i++) Y.push_back(P[i].y);
    sort(Y.begin(), Y.end());
    Y.resize(unique(Y.begin(), Y.end())-Y.begin());
    for(int i=1; i<=n; i++) P[i].y=lower_bound(Y.begin(), Y.end(), P[i].y)-Y.begin()+1;

    vector<int> Z;
    for(int i=1; i<=n; i++) Z.push_back(P[i].z);
    sort(Z.begin(), Z.end());
    Z.resize(unique(Z.begin(), Z.end())-Z.begin());
    for(int i=1; i<=n; i++) P[i].z=lower_bound(Z.begin(), Z.end(), P[i].z)-Z.begin()+1;

    sort(P+1, P+n+1, [](pt3 &a, pt3 &b){
        return a.z<b.z;
    });

    for(int i=1; i<=n; i++) Stair[i].init();
    Stair[0].S.insert({0,0});
    int ans=0;

    for(int i=1; i<=n; i++){
        pt2 p={P[i].x, P[i].y};
        int s=0, e=n;
        while(s<e){
            int m=(s+e+1)/2;
            if(Stair[m].valid(p)) s=m;
            else e=m-1;
        }
        ans=max(ans, s+1);
        Stair[s+1].put(p);
    }
    cout<<ans;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>m>>n;
    for(int i=1; i<=n; i++) cin>>P[i].x;
    for(int i=1; i<=n; i++) cin>>P[i].y;
    if(m==2) for(int i=1; i<=n; i++) P[i].z=P[i].y;
    else for(int i=1; i<=n; i++) cin>>P[i].z;
    solve3();
    return 0;
}

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