oj.uz

Submission #65663

# Submission time Handle Problem Language Result Execution time Memory
65663 2018-08-08T11:09:16 Z imeimi2000 None (KOI18_matrix) C++17
100 / 100
 1010 ms 10620 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int n, m;
struct column {
    int x[3];
    int dp = 1;
    bool operator<(const column &p) const {
        return x[1] < p.x[1];
    }
} cs[200000];

int cp[200000];
int seg[200001];

int find(int x, int n) {
    return lower_bound(cp, cp + n, x) - cp + 1;
}

int segn;
void init(int n) {
    segn = n;
    for (int i = 0; i <= n; ++i) seg[i] = 0;
}

void update(int i, int x) {
    while (i <= segn) {
        seg[i] = max(seg[i], x);
        i += i & -i;
    }
}

int query(int i) {
    int ret = 0;
    while (i) {
        ret = max(ret, seg[i]);
        i -= i & -i;
    }
    return ret;
}

void dnc(int s, int e) {
    if (s == e) return;
    int m = (s + e) / 2;
    int mx = cs[m].x[0];
    dnc(s, m);
    int tp = 0;
    for (int i = s; i <= e; ++i) {
        cp[tp++] = cs[i].x[2];
    }
    sort(cp, cp + tp);
    tp = unique(cp, cp + tp) - cp;
    init(tp);
    sort(cs + (m + 1), cs + (e + 1));
    for (int i = m + 1, j = s; i <= e; ++i) {
        while (j <= m && cs[j].x[1] <= cs[i].x[1]) 
            {
            update(find(cs[j].x[2], tp), cs[j].dp);
            ++j;
        }
        cs[i].dp = max(cs[i].dp, query(find(cs[i].x[2], tp)) + 1);
    }
    
	sort(cs + (m + 1), cs + (e + 1), [&](const column &x, const column &y) {
        return x.x[0] < y.x[0];
	});
	dnc(m + 1, e);
	sort(cs + s, cs + (e + 1));
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> m >> n;
	for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> cs[j].x[i];
        }
	}
	sort(cs, cs + n, [&](const column &x, const column &y) {
        return x.x[0] < y.x[0];
	});
	dnc(0, n - 1);
	int ans = 0;
	for (int i = 0; i < n; ++i) {
        ans = max(ans, cs[i].dp);
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message

matrix.cpp: In function 'void dnc(int, int)':
matrix.cpp:62:9: warning: unused variable 'mx' [-Wunused-variable]
     int mx = cs[m].x[0];
         ^~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3704 KB Output is correct
2 Correct 18 ms 3992 KB Output is correct
3 Correct 19 ms 4208 KB Output is correct
4 Correct 17 ms 4464 KB Output is correct
5 Correct 22 ms 4732 KB Output is correct
6 Correct 13 ms 4856 KB Output is correct
7 Correct 21 ms 5056 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5368 KB Output is correct
2 Correct 28 ms 5608 KB Output is correct
3 Correct 34 ms 5608 KB Output is correct
4 Correct 36 ms 5680 KB Output is correct
5 Correct 30 ms 5680 KB Output is correct
6 Correct 20 ms 5712 KB Output is correct
7 Correct 33 ms 5712 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3704 KB Output is correct
2 Correct 18 ms 3992 KB Output is correct
3 Correct 19 ms 4208 KB Output is correct
4 Correct 17 ms 4464 KB Output is correct
5 Correct 22 ms 4732 KB Output is correct
6 Correct 13 ms 4856 KB Output is correct
7 Correct 21 ms 5056 KB Output is correct
8 Correct 477 ms 6416 KB Output is correct
9 Correct 457 ms 6496 KB Output is correct
10 Correct 310 ms 6496 KB Output is correct
11 Correct 202 ms 6496 KB Output is correct
12 Correct 455 ms 6496 KB Output is correct
13 Correct 247 ms 6496 KB Output is correct
14 Correct 386 ms 6496 KB Output is correct
15 Correct 190 ms 6496 KB Output is correct
16 Correct 231 ms 6496 KB Output is correct
17 Correct 275 ms 6496 KB Output is correct
18 Correct 296 ms 6496 KB Output is correct
19 Correct 364 ms 6544 KB Output is correct
20 Correct 504 ms 6544 KB Output is correct

Subtask #4
62.0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5368 KB Output is correct
2 Correct 28 ms 5608 KB Output is correct
3 Correct 34 ms 5608 KB Output is correct
4 Correct 36 ms 5680 KB Output is correct
5 Correct 30 ms 5680 KB Output is correct
6 Correct 20 ms 5712 KB Output is correct
7 Correct 33 ms 5712 KB Output is correct
8 Correct 757 ms 9236 KB Output is correct
9 Correct 781 ms 10620 KB Output is correct
10 Correct 598 ms 10620 KB Output is correct
11 Correct 470 ms 10620 KB Output is correct
12 Correct 568 ms 10620 KB Output is correct
13 Correct 653 ms 10620 KB Output is correct
14 Correct 876 ms 10620 KB Output is correct
15 Correct 491 ms 10620 KB Output is correct
16 Correct 555 ms 10620 KB Output is correct
17 Correct 776 ms 10620 KB Output is correct
18 Correct 1010 ms 10620 KB Output is correct
19 Correct 921 ms 10620 KB Output is correct
20 Correct 770 ms 10620 KB Output is correct
21 Correct 459 ms 10620 KB Output is correct
22 Correct 987 ms 10620 KB Output is correct
23 Correct 792 ms 10620 KB Output is correct
24 Correct 964 ms 10620 KB Output is correct
25 Correct 951 ms 10620 KB Output is correct
26 Correct 863 ms 10620 KB Output is correct
27 Correct 549 ms 10620 KB Output is correct
28 Correct 494 ms 10620 KB Output is correct
29 Correct 768 ms 10620 KB Output is correct
30 Correct 761 ms 10620 KB Output is correct
31 Correct 850 ms 10620 KB Output is correct
32 Correct 737 ms 10620 KB Output is correct