답안 #67560 :: oj.uz

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

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

#	결과	실행 시간	메모리	Grader output
1	Correct	47 ms	7032 KB	Output is correct
2	Correct	32 ms	7140 KB	Output is correct
3	Correct	33 ms	7220 KB	Output is correct
4	Correct	35 ms	7268 KB	Output is correct
5	Correct	41 ms	7268 KB	Output is correct
6	Correct	31 ms	7268 KB	Output is correct
7	Correct	31 ms	7268 KB	Output is correct

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	9036 KB	Output is correct
2	Correct	35 ms	9036 KB	Output is correct
3	Correct	50 ms	12244 KB	Output is correct
4	Correct	89 ms	14796 KB	Output is correct
5	Correct	39 ms	14796 KB	Output is correct
6	Correct	29 ms	14796 KB	Output is correct
7	Correct	67 ms	14796 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	47 ms	7032 KB	Output is correct
2	Correct	32 ms	7140 KB	Output is correct
3	Correct	33 ms	7220 KB	Output is correct
4	Correct	35 ms	7268 KB	Output is correct
5	Correct	41 ms	7268 KB	Output is correct
6	Correct	31 ms	7268 KB	Output is correct
7	Correct	31 ms	7268 KB	Output is correct
8	Correct	1855 ms	173860 KB	Output is correct
9	Correct	1657 ms	173960 KB	Output is correct
10	Correct	832 ms	173960 KB	Output is correct
11	Correct	776 ms	173960 KB	Output is correct
12	Correct	1090 ms	173964 KB	Output is correct
13	Correct	837 ms	173964 KB	Output is correct
14	Correct	930 ms	174000 KB	Output is correct
15	Correct	741 ms	174000 KB	Output is correct
16	Correct	846 ms	174000 KB	Output is correct
17	Correct	766 ms	174000 KB	Output is correct
18	Correct	794 ms	174000 KB	Output is correct
19	Correct	870 ms	174000 KB	Output is correct
20	Correct	1981 ms	174060 KB	Output is correct

Subtask #4
62.0 / 62.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	9036 KB	Output is correct
2	Correct	35 ms	9036 KB	Output is correct
3	Correct	50 ms	12244 KB	Output is correct
4	Correct	89 ms	14796 KB	Output is correct
5	Correct	39 ms	14796 KB	Output is correct
6	Correct	29 ms	14796 KB	Output is correct
7	Correct	67 ms	14796 KB	Output is correct
8	Correct	990 ms	238156 KB	Output is correct
9	Correct	1619 ms	330856 KB	Output is correct
10	Correct	853 ms	330856 KB	Output is correct
11	Correct	819 ms	330856 KB	Output is correct
12	Correct	1572 ms	456956 KB	Output is correct
13	Correct	858 ms	456956 KB	Output is correct
14	Correct	1567 ms	456956 KB	Output is correct
15	Correct	801 ms	456956 KB	Output is correct
16	Correct	827 ms	456956 KB	Output is correct
17	Correct	1549 ms	456956 KB	Output is correct
18	Correct	3785 ms	456956 KB	Output is correct
19	Correct	2468 ms	456956 KB	Output is correct
20	Correct	1248 ms	456956 KB	Output is correct
21	Correct	883 ms	456956 KB	Output is correct
22	Correct	3635 ms	456956 KB	Output is correct
23	Correct	1708 ms	456956 KB	Output is correct
24	Correct	2221 ms	457176 KB	Output is correct
25	Correct	2455 ms	457176 KB	Output is correct
26	Correct	1758 ms	457176 KB	Output is correct
27	Correct	1540 ms	457176 KB	Output is correct
28	Correct	805 ms	457176 KB	Output is correct
29	Correct	1497 ms	457176 KB	Output is correct
30	Correct	1609 ms	457176 KB	Output is correct
31	Correct	1867 ms	457176 KB	Output is correct
32	Correct	1524 ms	457176 KB	Output is correct

답안 #67560

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