oj.uz

Submission #67505

# Submission time Handle Problem Language Result Execution time Memory
67505 2018-08-14T11:29:20 Z h0ngjun7 None (KOI18_matrix) C++17
38 / 100
 4000 ms 457960 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) {
    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 x, int y, int z) {
    while (true) {
        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;
            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 y) {
    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;
        }
        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, 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() {
    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++) {
        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);
    }
    cout << ans << "\n";
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 7032 KB Output is correct
2 Correct 32 ms 7064 KB Output is correct
3 Correct 35 ms 7096 KB Output is correct
4 Correct 32 ms 7096 KB Output is correct
5 Correct 37 ms 7224 KB Output is correct
6 Correct 30 ms 7300 KB Output is correct
7 Correct 31 ms 7300 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 8908 KB Output is correct
2 Correct 37 ms 8908 KB Output is correct
3 Correct 61 ms 12292 KB Output is correct
4 Correct 83 ms 14724 KB Output is correct
5 Correct 45 ms 14724 KB Output is correct
6 Correct 38 ms 14724 KB Output is correct
7 Correct 66 ms 14724 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 7032 KB Output is correct
2 Correct 32 ms 7064 KB Output is correct
3 Correct 35 ms 7096 KB Output is correct
4 Correct 32 ms 7096 KB Output is correct
5 Correct 37 ms 7224 KB Output is correct
6 Correct 30 ms 7300 KB Output is correct
7 Correct 31 ms 7300 KB Output is correct
8 Correct 1703 ms 174112 KB Output is correct
9 Correct 1454 ms 174116 KB Output is correct
10 Correct 789 ms 174364 KB Output is correct
11 Correct 703 ms 174364 KB Output is correct
12 Correct 1082 ms 174548 KB Output is correct
13 Correct 766 ms 174548 KB Output is correct
14 Correct 918 ms 174548 KB Output is correct
15 Correct 726 ms 174548 KB Output is correct
16 Correct 813 ms 174548 KB Output is correct
17 Correct 862 ms 174548 KB Output is correct
18 Correct 887 ms 174548 KB Output is correct
19 Correct 888 ms 174548 KB Output is correct
20 Correct 2015 ms 174548 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 8908 KB Output is correct
2 Correct 37 ms 8908 KB Output is correct
3 Correct 61 ms 12292 KB Output is correct
4 Correct 83 ms 14724 KB Output is correct
5 Correct 45 ms 14724 KB Output is correct
6 Correct 38 ms 14724 KB Output is correct
7 Correct 66 ms 14724 KB Output is correct
8 Correct 1035 ms 238556 KB Output is correct
9 Correct 1730 ms 331492 KB Output is correct
10 Correct 924 ms 331492 KB Output is correct
11 Correct 782 ms 331492 KB Output is correct
12 Correct 1847 ms 457324 KB Output is correct
13 Correct 988 ms 457324 KB Output is correct
14 Correct 2016 ms 457324 KB Output is correct
15 Correct 862 ms 457324 KB Output is correct
16 Correct 830 ms 457324 KB Output is correct
17 Correct 1779 ms 457324 KB Output is correct
18 Correct 3570 ms 457324 KB Output is correct
19 Correct 2131 ms 457960 KB Output is correct
20 Correct 1331 ms 457960 KB Output is correct
21 Correct 879 ms 457960 KB Output is correct
22 Execution timed out 4056 ms 457960 KB Time limit exceeded
23 Halted 0 ms 0 KB -