Submission #65663

#	Time	Username	Problem	Language	Result	Execution time	Memory
65663		imeimi2000	조화행렬 (KOI18_matrix)	C++17	100 / 100	1010 ms	10620 KiB

matrix

#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 (stderr)

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 / 14
• Subtask 2: 9 / 9
• Subtask 3: 15 / 15
• Subtask 4: 62 / 62