Submission #67337

#	Time	Username	Problem	Language	Result	Execution time	Memory
67337		h0ngjun7	조화행렬 (KOI18_matrix)	C++17	38 / 100	4070 ms	456896 KiB

matrix

#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;

void updy(int cur, int s, int e, int y, int z) {
    if (s == e) {
        segy[cur].w = z;
        return;
    }
    int m = (s+e)/2;
    if (y <= m) {
        if (segy[cur].l == 0) segy[cur].l = ++segyn;
        updy(segy[cur].l, s, m, y, z);
    } else {
        if (segy[cur].r == 0) segy[cur].r = ++segyn;
        updy(segy[cur].r, m+1, e, y, z);
    }
    segy[cur].w = max(segy[ segy[cur].l ].w, segy[ segy[cur].r ].w);
}

void updx(int cur, int s, int e, int x, int y, int z) {
    if (segx[cur].p == 0) segx[cur].p = ++segyn;
    updy(segx[cur].p, 1, XN[3], y, z);
    if (s == e) {
        return;
    }
    int m = (s+e)/2;
    if (x <= m) {
        if (segx[cur].l == 0) segx[cur].l = ++segxn;
        updx(segx[cur].l, s, m, x, y, z);
    } else {
        if (segx[cur].r == 0) segx[cur].r = ++segxn;
        updx(segx[cur].r, m+1, e, x, y, z);
    }
}

int queryy(int cur, int s, int e, int y) {
    if (cur == 0 || e < 1 || y < s || s > e) {
        return 0;
    }
    if (1 <= s && e <= y) return segy[cur].w;
    int m = (s+e)/2;
    if (y <= m) return queryy(segy[cur].l, s, m, y);
    return max(segy[segy[cur].l].w, queryy(segy[cur].r, m+1, e, y));
}

int queryx(int cur, int s, int e, int x, int y) {
    if (cur == 0 || e < 1 || x < s || s > e) {
        return 0;
    }
    if (1 <= s && e <= x) return queryy(segx[cur].p, 1, XN[3], y);
    int m = (s+e)/2;
    if (x <= m) return queryx(segx[cur].l, s, m, x, y);
    return max(queryx(segx[cur].l, s, m, x, y), queryx(segx[cur].r, m+1, e, x, y));
}

int main() {
    scanf("%d%d",&N,&M);
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            scanf("%d",&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++) {
        int best = queryx(1, 1, XN[2], C[2][i], C[3][i]);
        updx(1, 1, XN[2], C[2][i], C[3][i], best+1);
        ans = max(ans, best+1);
    }
    printf("%d\n", ans);
}

Compilation message (stderr)

matrix.cpp: In function 'int main()':
matrix.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&N,&M);
     ~~~~~^~~~~~~~~~~~~~
matrix.cpp:75:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&A[i][j]);
             ~~~~~^~~~~~~~~~~~~~~

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