Submission #67560

#	Time	Username	Problem	Language	Result	Execution time	Memory
67560		h0ngjun7	조화행렬 (KOI18_matrix)	C++17	100 / 100	3785 ms	457176 KiB

matrix

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 200005;
 
int N, M;
int A[4][MAXN], P[MAXN], X[4][MAXN], XN[4];
int C[4][MAXN];
int D[MAXN], ans;
 
struct SEGX {
    int l, r, p;
} segx[MAXN*4]; int segxn = 1;
 
struct SEGY {
    int l, r, w;
} segy[MAXN*200]; int segyn;
 
int x, y;
 
void updy(int cur, int s, int e, int z) {
    while (true) {
        segy[cur].w = max(segy[cur].w, z);
        if (s == e) return;
        int m = (s+e)/2;
        if (y <= m) {
            if (segy[cur].l == 0) segy[cur].l = ++segyn;
            cur = segy[cur].l;
            e = m;
        } else {
            if (segy[cur].r == 0) segy[cur].r = ++segyn;
            cur = segy[cur].r;
            s = m+1;
        }
    }
}
 
void updx(int cur, int s, int e, int z) {
    while (true) {
        if (segx[cur].p == 0) segx[cur].p = ++segyn;
        updy(segx[cur].p, 1, XN[3], z);
        if (s == e) return;
        int m = (s+e)/2;
        if (x <= m) {
            if (segx[cur].l == 0) segx[cur].l = ++segxn;
            cur = segx[cur].l;
            e = m;
        } else {
            if (segx[cur].r == 0) segx[cur].r = ++segxn;
            cur = segx[cur].r;
            s = m+1;
        }
    }
}
 
int queryy(int cur, int s, int e) {
    int ret = 0;
    while (true) {
        if (cur == 0 || e < 1 || y < s || s > e) break;
        if (1 <= s && e <= y) {
            ret = max(ret, segy[cur].w);
            break;
        }
        if (segy[cur].w <= ret) break;
        int m = (s+e)/2;
        if (y <= m) cur = segy[cur].l, e = m;
        else {
            ret = max(segy[segy[cur].l].w, ret);
            cur = segy[cur].r;
            s = m+1;
        }
    }
    return ret;
}
 
int queryx(int cur, int s, int e) {
    if (cur == 0 || e < 1 || x < s || s > e) return 0;
    if (1 <= s && e <= x) return queryy(segx[cur].p, 1, XN[3]);
    int m = (s+e)/2;
    if (x <= m) return queryx(segx[cur].l, s, m);
    return max(queryx(segx[cur].l, s, m), queryx(segx[cur].r, m+1, e));
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> A[i][j];
            P[j] = j;
            X[i][XN[i]++] = A[i][j];
        }
    }
    if (N == 2) {
        for (int j = 1; j <= M; j++) {
            A[N+1][j] = A[N][j];
            X[N+1][XN[N+1]++] = A[N][j];
        }
        N++;
    }
    for (int i = 2; i <= N; i++) {
        sort(X[i], X[i]+XN[i]);
        XN[i] = unique(X[i], X[i]+XN[i])-X[i];
    }
    sort(P+1, P+M+1, [&](int x, int y) {
       return A[1][x] < A[1][y]; 
    });
    for (int i = 2; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            C[i][j] = (lower_bound(X[i], X[i]+XN[i], A[i][P[j]]) - X[i]) + 1;
        }
    }
    for (int i = 1; i <= M; i++) {
        x = C[2][i], y = C[3][i];
        int best = queryx(1, 1, XN[2]);
        updx(1, 1, XN[2], best+1);
        ans = max(ans, best+1);
    }
    cout << ans << "\n";
}

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