Submission #67198

#TimeUsernameProblemLanguageResultExecution timeMemory
67198h0ngjun7조화행렬 (KOI18_matrix)C++17
38 / 100
4147 ms678200 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 200005; int N, M; int A[4][MAXN], P[MAXN], X[3*MAXN], XN; int C[4][MAXN]; int D[MAXN], ans; struct SEGX { int l, r, p; } segx[MAXN*20]; int segxn = 1; struct SEGY { int l, r, w; } segy[MAXN*20*20]; 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, 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; return max(queryy(segy[cur].l, s, m, y), 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) { int ret = queryy(segx[cur].p, 1, XN, y); return ret; } int m = (s+e)/2; 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[XN++] = A[i][j]; } } sort(X, X+XN); XN = unique(X, X+XN)-X; if (N == 2) { for (int j = 1; j <= M; j++) { A[N+1][j] = A[N][j]; } N++; } sort(P+1, P+M+1, [&](int x, int y) { return A[1][x] < A[1][y]; }); for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { C[i][j] = (lower_bound(X, X+XN, A[i][P[j]]) - X) + 1; } } for (int i = 1; i <= M; i++) { int best = queryx(1, 1, XN, C[2][i], C[3][i]); updx(1, 1, XN, C[2][i], C[3][i], best+1); ans = max(ans, best+1); } printf("%d\n", ans); }

Compilation message (stderr)

matrix.cpp: In function 'int main()':
matrix.cpp:75: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:78:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&A[i][j]);
             ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...