oj.uz

Submission #67557

# Submission time Handle Problem Language Result Execution time Memory
67557 2018-08-15T00:22:51 Z h0ngjun7 None (KOI18_matrix) C++17
100 / 100
 3905 ms 458156 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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