답안 #67557 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67557	2018-08-15T00:22:51 Z	h0ngjun7	조화행렬 (KOI18_matrix)	C++17	100 / 100	3905 ms	458156 KB

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;

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.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	45 ms	7236 KB	Output is correct
2	Correct	32 ms	7236 KB	Output is correct
3	Correct	32 ms	7236 KB	Output is correct
4	Correct	33 ms	7236 KB	Output is correct
5	Correct	35 ms	7236 KB	Output is correct
6	Correct	31 ms	7236 KB	Output is correct
7	Correct	33 ms	7272 KB	Output is correct

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	38 ms	9044 KB	Output is correct
2	Correct	34 ms	9044 KB	Output is correct
3	Correct	55 ms	12380 KB	Output is correct
4	Correct	79 ms	14744 KB	Output is correct
5	Correct	46 ms	14744 KB	Output is correct
6	Correct	33 ms	14744 KB	Output is correct
7	Correct	56 ms	14744 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	45 ms	7236 KB	Output is correct
2	Correct	32 ms	7236 KB	Output is correct
3	Correct	32 ms	7236 KB	Output is correct
4	Correct	33 ms	7236 KB	Output is correct
5	Correct	35 ms	7236 KB	Output is correct
6	Correct	31 ms	7236 KB	Output is correct
7	Correct	33 ms	7272 KB	Output is correct
8	Correct	1810 ms	173932 KB	Output is correct
9	Correct	1496 ms	174024 KB	Output is correct
10	Correct	820 ms	174416 KB	Output is correct
11	Correct	767 ms	174416 KB	Output is correct
12	Correct	1282 ms	174416 KB	Output is correct
13	Correct	786 ms	174420 KB	Output is correct
14	Correct	954 ms	174504 KB	Output is correct
15	Correct	730 ms	174504 KB	Output is correct
16	Correct	806 ms	174504 KB	Output is correct
17	Correct	733 ms	174504 KB	Output is correct
18	Correct	789 ms	174504 KB	Output is correct
19	Correct	816 ms	174504 KB	Output is correct
20	Correct	1766 ms	174504 KB	Output is correct

Subtask #4
62.0 / 62.0

#	결과	실행 시간	메모리	Grader output
1	Correct	38 ms	9044 KB	Output is correct
2	Correct	34 ms	9044 KB	Output is correct
3	Correct	55 ms	12380 KB	Output is correct
4	Correct	79 ms	14744 KB	Output is correct
5	Correct	46 ms	14744 KB	Output is correct
6	Correct	33 ms	14744 KB	Output is correct
7	Correct	56 ms	14744 KB	Output is correct
8	Correct	981 ms	238660 KB	Output is correct
9	Correct	1839 ms	331316 KB	Output is correct
10	Correct	928 ms	331316 KB	Output is correct
11	Correct	898 ms	331316 KB	Output is correct
12	Correct	2116 ms	457336 KB	Output is correct
13	Correct	931 ms	457336 KB	Output is correct
14	Correct	1565 ms	457336 KB	Output is correct
15	Correct	794 ms	457336 KB	Output is correct
16	Correct	850 ms	457336 KB	Output is correct
17	Correct	1825 ms	457336 KB	Output is correct
18	Correct	3905 ms	457336 KB	Output is correct
19	Correct	2763 ms	458156 KB	Output is correct
20	Correct	1122 ms	458156 KB	Output is correct
21	Correct	859 ms	458156 KB	Output is correct
22	Correct	3109 ms	458156 KB	Output is correct
23	Correct	1563 ms	458156 KB	Output is correct
24	Correct	2408 ms	458156 KB	Output is correct
25	Correct	2623 ms	458156 KB	Output is correct
26	Correct	2101 ms	458156 KB	Output is correct
27	Correct	1639 ms	458156 KB	Output is correct
28	Correct	795 ms	458156 KB	Output is correct
29	Correct	1618 ms	458156 KB	Output is correct
30	Correct	1591 ms	458156 KB	Output is correct
31	Correct	1824 ms	458156 KB	Output is correct
32	Correct	1555 ms	458156 KB	Output is correct

답안 #67557

Compilation message

Subtask #1 14.0 / 14.0

Subtask #2 9.0 / 9.0

Subtask #3 15.0 / 15.0

Subtask #4 62.0 / 62.0

Subtask #1
14.0 / 14.0

Subtask #2
9.0 / 9.0

Subtask #3
15.0 / 15.0

Subtask #4
62.0 / 62.0