oj.uz

Submission #67336

# Submission time Handle Problem Language Result Execution time Memory
67336 2018-08-14T03:21:30 Z h0ngjun7 None (KOI18_matrix) C++17
38 / 100
 2861 ms 379396 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*19*4]; 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 51 ms 7032 KB Output is correct
2 Correct 39 ms 7032 KB Output is correct
3 Correct 42 ms 7032 KB Output is correct
4 Correct 35 ms 7084 KB Output is correct
5 Correct 51 ms 7112 KB Output is correct
6 Correct 35 ms 7164 KB Output is correct
7 Correct 40 ms 7172 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 8964 KB Output is correct
2 Correct 44 ms 8964 KB Output is correct
3 Correct 56 ms 12244 KB Output is correct
4 Correct 83 ms 14736 KB Output is correct
5 Correct 52 ms 14736 KB Output is correct
6 Correct 48 ms 14736 KB Output is correct
7 Correct 73 ms 14736 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 7032 KB Output is correct
2 Correct 39 ms 7032 KB Output is correct
3 Correct 42 ms 7032 KB Output is correct
4 Correct 35 ms 7084 KB Output is correct
5 Correct 51 ms 7112 KB Output is correct
6 Correct 35 ms 7164 KB Output is correct
7 Correct 40 ms 7172 KB Output is correct
8 Correct 2861 ms 173832 KB Output is correct
9 Correct 2308 ms 173896 KB Output is correct
10 Correct 925 ms 173908 KB Output is correct
11 Correct 805 ms 173908 KB Output is correct
12 Correct 1717 ms 173908 KB Output is correct
13 Correct 967 ms 173908 KB Output is correct
14 Correct 1144 ms 173920 KB Output is correct
15 Correct 809 ms 173920 KB Output is correct
16 Correct 997 ms 174068 KB Output is correct
17 Correct 911 ms 174068 KB Output is correct
18 Correct 1026 ms 174068 KB Output is correct
19 Correct 955 ms 174068 KB Output is correct
20 Correct 2267 ms 174068 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 8964 KB Output is correct
2 Correct 44 ms 8964 KB Output is correct
3 Correct 56 ms 12244 KB Output is correct
4 Correct 83 ms 14736 KB Output is correct
5 Correct 52 ms 14736 KB Output is correct
6 Correct 48 ms 14736 KB Output is correct
7 Correct 73 ms 14736 KB Output is correct
8 Runtime error 1182 ms 379396 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -