oj.uz

Submission #67335

# Submission time Handle Problem Language Result Execution time Memory
67335 2018-08-14T03:11:38 Z h0ngjun7 None (KOI18_matrix) C++17
38 / 100
 4000 ms 471032 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*18]; int segxn = 1;

struct SEGY {
    int l, r, w;
} segy[MAXN*18*18]; 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 54 ms 7160 KB Output is correct
2 Correct 36 ms 7424 KB Output is correct
3 Correct 43 ms 7728 KB Output is correct
4 Correct 42 ms 7932 KB Output is correct
5 Correct 50 ms 8236 KB Output is correct
6 Correct 37 ms 8332 KB Output is correct
7 Correct 41 ms 8728 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 10688 KB Output is correct
2 Correct 52 ms 10688 KB Output is correct
3 Correct 57 ms 14600 KB Output is correct
4 Correct 80 ms 17196 KB Output is correct
5 Correct 55 ms 17196 KB Output is correct
6 Correct 44 ms 17196 KB Output is correct
7 Correct 78 ms 17540 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 7160 KB Output is correct
2 Correct 36 ms 7424 KB Output is correct
3 Correct 43 ms 7728 KB Output is correct
4 Correct 42 ms 7932 KB Output is correct
5 Correct 50 ms 8236 KB Output is correct
6 Correct 37 ms 8332 KB Output is correct
7 Correct 41 ms 8728 KB Output is correct
8 Correct 2407 ms 181356 KB Output is correct
9 Correct 1935 ms 185160 KB Output is correct
10 Correct 957 ms 188028 KB Output is correct
11 Correct 841 ms 188028 KB Output is correct
12 Correct 1540 ms 188028 KB Output is correct
13 Correct 1012 ms 188080 KB Output is correct
14 Correct 1162 ms 188080 KB Output is correct
15 Correct 840 ms 188080 KB Output is correct
16 Correct 935 ms 188080 KB Output is correct
17 Correct 982 ms 188080 KB Output is correct
18 Correct 924 ms 188080 KB Output is correct
19 Correct 972 ms 188080 KB Output is correct
20 Correct 2310 ms 188080 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 10688 KB Output is correct
2 Correct 52 ms 10688 KB Output is correct
3 Correct 57 ms 14600 KB Output is correct
4 Correct 80 ms 17196 KB Output is correct
5 Correct 55 ms 17196 KB Output is correct
6 Correct 44 ms 17196 KB Output is correct
7 Correct 78 ms 17540 KB Output is correct
8 Correct 1338 ms 252104 KB Output is correct
9 Correct 2311 ms 345004 KB Output is correct
10 Correct 1184 ms 345004 KB Output is correct
11 Correct 1048 ms 345004 KB Output is correct
12 Correct 2039 ms 471032 KB Output is correct
13 Correct 1042 ms 471032 KB Output is correct
14 Correct 2452 ms 471032 KB Output is correct
15 Correct 1141 ms 471032 KB Output is correct
16 Correct 1000 ms 471032 KB Output is correct
17 Correct 2027 ms 471032 KB Output is correct
18 Execution timed out 4043 ms 471032 KB Time limit exceeded
19 Halted 0 ms 0 KB -