oj.uz

Submission #67198

# Submission time Handle Problem Language Result Execution time Memory
67198 2018-08-13T14:52:54 Z h0ngjun7 None (KOI18_matrix) C++17
38 / 100
 4000 ms 678200 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;

int N, M;
int A[4][MAXN], P[MAXN], X[3*MAXN], XN;
int C[4][MAXN];
int D[MAXN], ans;

struct SEGX {
    int l, r, p;
} segx[MAXN*20]; int segxn = 1;

struct SEGY {
    int l, r, w;
} segy[MAXN*20*20]; 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, 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;
    return max(queryy(segy[cur].l, s, m, y), 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) {
        int ret = queryy(segx[cur].p, 1, XN, y);
        return ret;
    }
    int m = (s+e)/2;
    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[XN++] = A[i][j];
        }
    }
    sort(X, X+XN);
    XN = unique(X, X+XN)-X;
    if (N == 2) {
        for (int j = 1; j <= M; j++) {
            A[N+1][j] = A[N][j];
        }
        N++;
    }
    sort(P+1, P+M+1, [&](int x, int y) {
       return A[1][x] < A[1][y]; 
    });
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            C[i][j] = (lower_bound(X, X+XN, A[i][P[j]]) - X) + 1;
        }
    }
    for (int i = 1; i <= M; i++) {
        int best = queryx(1, 1, XN, C[2][i], C[3][i]);
        updx(1, 1, XN, 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:75: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:78: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 75 ms 9848 KB Output is correct
2 Correct 50 ms 10280 KB Output is correct
3 Correct 61 ms 10548 KB Output is correct
4 Correct 48 ms 10744 KB Output is correct
5 Correct 66 ms 10988 KB Output is correct
6 Correct 47 ms 11184 KB Output is correct
7 Correct 61 ms 11444 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 15664 KB Output is correct
2 Correct 53 ms 15664 KB Output is correct
3 Correct 92 ms 19980 KB Output is correct
4 Correct 119 ms 22716 KB Output is correct
5 Correct 66 ms 22716 KB Output is correct
6 Correct 51 ms 22716 KB Output is correct
7 Correct 148 ms 23112 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 9848 KB Output is correct
2 Correct 50 ms 10280 KB Output is correct
3 Correct 61 ms 10548 KB Output is correct
4 Correct 48 ms 10744 KB Output is correct
5 Correct 66 ms 10988 KB Output is correct
6 Correct 47 ms 11184 KB Output is correct
7 Correct 61 ms 11444 KB Output is correct
8 Correct 3521 ms 251300 KB Output is correct
9 Correct 3102 ms 255132 KB Output is correct
10 Correct 1399 ms 259104 KB Output is correct
11 Correct 1222 ms 263072 KB Output is correct
12 Correct 1934 ms 266932 KB Output is correct
13 Correct 1368 ms 270684 KB Output is correct
14 Correct 1530 ms 274444 KB Output is correct
15 Correct 1305 ms 278212 KB Output is correct
16 Correct 1272 ms 282068 KB Output is correct
17 Correct 1354 ms 286216 KB Output is correct
18 Correct 1198 ms 289904 KB Output is correct
19 Correct 1334 ms 293548 KB Output is correct
20 Correct 3230 ms 297488 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 15664 KB Output is correct
2 Correct 53 ms 15664 KB Output is correct
3 Correct 92 ms 19980 KB Output is correct
4 Correct 119 ms 22716 KB Output is correct
5 Correct 66 ms 22716 KB Output is correct
6 Correct 51 ms 22716 KB Output is correct
7 Correct 148 ms 23112 KB Output is correct
8 Correct 1727 ms 422920 KB Output is correct
9 Correct 2917 ms 526288 KB Output is correct
10 Correct 1536 ms 526288 KB Output is correct
11 Correct 1437 ms 526288 KB Output is correct
12 Correct 2924 ms 678200 KB Output is correct
13 Correct 1485 ms 678200 KB Output is correct
14 Correct 3092 ms 678200 KB Output is correct
15 Correct 1466 ms 678200 KB Output is correct
16 Correct 1546 ms 678200 KB Output is correct
17 Correct 2973 ms 678200 KB Output is correct
18 Execution timed out 4147 ms 678200 KB Time limit exceeded
19 Halted 0 ms 0 KB -