Submission #67505

#TimeUsernameProblemLanguageResultExecution timeMemory
67505h0ngjun7조화행렬 (KOI18_matrix)C++17
38 / 100
4056 ms457960 KiB
#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"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...