# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
127175 | 2019-07-09T03:42:26 Z | arnold518 | None (KOI18_matrix) | C++14 | 4000 ms | 17444 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 2e5; int M, N, dp[MAXN+10], ans; struct tup { int a, b, c; bool operator < (const tup& p) { return a<p.a; } }; tup A[MAXN+10]; struct BIT { vector<int> tree; BIT() : tree(N+10, 0) {} void update(int i, int val) { for(; i<=N; i+=(i&-i)) tree[i]=max(tree[i], val); } int query(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret=max(ret, tree[i]); return ret; } }; void solve(int s, int e) { int i, j; if(s==e) { dp[s]=max(dp[s], 1); return; } int mid=s+e>>1; solve(s, mid); vector<tup> L, R; for(i=s; i<=mid; i++) L.push_back({A[i].b, A[i].c, dp[i]}); for(i=mid+1; i<=e; i++) R.push_back({A[i].b, A[i].c, i}); sort(L.begin(), L.end()); sort(R.begin(), R.end()); BIT bit; int pt=0; for(i=0; i<R.size(); i++) { while(pt<L.size() && L[pt].a<R[i].a) bit.update(L[pt].b, L[pt].c), pt++; dp[R[i].c]=max(dp[R[i].c], bit.query(R[i].b)+1); } solve(mid+1, e); } int main() { int i, j; scanf("%d%d", &M, &N); vector<int> Vb, Vc; for(i=1; i<=N; i++) scanf("%d", &A[i].a); for(i=1; i<=N; i++) scanf("%d", &A[i].b), Vb.push_back(A[i].b); if(M==3) for(i=1; i<=N; i++) scanf("%d", &A[i].c), Vc.push_back(A[i].c); else for(i=1; i<=N; i++) A[i].c=A[i].a, Vc.push_back(A[i].c); sort(Vb.begin(), Vb.end()); sort(Vc.begin(), Vc.end()); for(i=1; i<=N; i++) A[i].b=lower_bound(Vb.begin(), Vb.end(), A[i].b)-Vb.begin()+1; for(i=1; i<=N; i++) A[i].c=lower_bound(Vc.begin(), Vc.end(), A[i].c)-Vc.begin()+1; sort(A+1, A+N+1); solve(1, N); for(i=1; i<=N; i++) ans=max(ans, dp[i]); printf("%d", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 103 ms | 1748 KB | Output is correct |
2 | Correct | 100 ms | 1612 KB | Output is correct |
3 | Correct | 100 ms | 1688 KB | Output is correct |
4 | Correct | 102 ms | 1656 KB | Output is correct |
5 | Correct | 101 ms | 1688 KB | Output is correct |
6 | Correct | 96 ms | 1688 KB | Output is correct |
7 | Correct | 99 ms | 1712 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 102 ms | 1724 KB | Output is correct |
2 | Correct | 101 ms | 1776 KB | Output is correct |
3 | Correct | 104 ms | 1716 KB | Output is correct |
4 | Correct | 104 ms | 1688 KB | Output is correct |
5 | Correct | 103 ms | 1716 KB | Output is correct |
6 | Correct | 98 ms | 1688 KB | Output is correct |
7 | Correct | 103 ms | 1816 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 103 ms | 1748 KB | Output is correct |
2 | Correct | 100 ms | 1612 KB | Output is correct |
3 | Correct | 100 ms | 1688 KB | Output is correct |
4 | Correct | 102 ms | 1656 KB | Output is correct |
5 | Correct | 101 ms | 1688 KB | Output is correct |
6 | Correct | 96 ms | 1688 KB | Output is correct |
7 | Correct | 99 ms | 1712 KB | Output is correct |
8 | Execution timed out | 4011 ms | 17444 KB | Time limit exceeded |
9 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 102 ms | 1724 KB | Output is correct |
2 | Correct | 101 ms | 1776 KB | Output is correct |
3 | Correct | 104 ms | 1716 KB | Output is correct |
4 | Correct | 104 ms | 1688 KB | Output is correct |
5 | Correct | 103 ms | 1716 KB | Output is correct |
6 | Correct | 98 ms | 1688 KB | Output is correct |
7 | Correct | 103 ms | 1816 KB | Output is correct |
8 | Execution timed out | 4014 ms | 17244 KB | Time limit exceeded |
9 | Halted | 0 ms | 0 KB | - |