oj.uz

Submission #67337

# Submission time Handle Problem Language Result Execution time Memory
67337 2018-08-14T03:22:34 Z h0ngjun7 None (KOI18_matrix) C++17
38 / 100
 4000 ms 456896 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;

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

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

# Verdict Execution time Memory Grader output
1 Correct 67 ms 6980 KB Output is correct
2 Correct 50 ms 7164 KB Output is correct
3 Correct 54 ms 7164 KB Output is correct
4 Correct 49 ms 7164 KB Output is correct
5 Correct 66 ms 7292 KB Output is correct
6 Correct 41 ms 7292 KB Output is correct
7 Correct 40 ms 7292 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 8864 KB Output is correct
2 Correct 51 ms 8864 KB Output is correct
3 Correct 69 ms 12472 KB Output is correct
4 Correct 120 ms 14796 KB Output is correct
5 Correct 58 ms 14796 KB Output is correct
6 Correct 41 ms 14796 KB Output is correct
7 Correct 99 ms 14796 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 6980 KB Output is correct
2 Correct 50 ms 7164 KB Output is correct
3 Correct 54 ms 7164 KB Output is correct
4 Correct 49 ms 7164 KB Output is correct
5 Correct 66 ms 7292 KB Output is correct
6 Correct 41 ms 7292 KB Output is correct
7 Correct 40 ms 7292 KB Output is correct
8 Correct 3228 ms 173948 KB Output is correct
9 Correct 2609 ms 173948 KB Output is correct
10 Correct 1107 ms 173948 KB Output is correct
11 Correct 1000 ms 173948 KB Output is correct
12 Correct 1780 ms 174060 KB Output is correct
13 Correct 1216 ms 174060 KB Output is correct
14 Correct 1392 ms 174060 KB Output is correct
15 Correct 1006 ms 174060 KB Output is correct
16 Correct 1070 ms 174060 KB Output is correct
17 Correct 1000 ms 174060 KB Output is correct
18 Correct 1128 ms 174060 KB Output is correct
19 Correct 1181 ms 174060 KB Output is correct
20 Correct 3312 ms 174060 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 8864 KB Output is correct
2 Correct 51 ms 8864 KB Output is correct
3 Correct 69 ms 12472 KB Output is correct
4 Correct 120 ms 14796 KB Output is correct
5 Correct 58 ms 14796 KB Output is correct
6 Correct 41 ms 14796 KB Output is correct
7 Correct 99 ms 14796 KB Output is correct
8 Correct 1544 ms 238036 KB Output is correct
9 Correct 2869 ms 330884 KB Output is correct
10 Correct 1139 ms 330884 KB Output is correct
11 Correct 1130 ms 330884 KB Output is correct
12 Correct 2792 ms 456896 KB Output is correct
13 Correct 1173 ms 456896 KB Output is correct
14 Correct 2141 ms 456896 KB Output is correct
15 Correct 958 ms 456896 KB Output is correct
16 Correct 954 ms 456896 KB Output is correct
17 Correct 2154 ms 456896 KB Output is correct
18 Execution timed out 4070 ms 456896 KB Time limit exceeded
19 Halted 0 ms 0 KB -