#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;
struct Fenwick{
int tree[202020];
void update(int x, int v){
x++;
while(x < 202020){
tree[x] = max(tree[x], v);
x += x & -x;
}
}
int query(int x){
x++;
int ret = 0;
while(x){
ret = max(ret, tree[x]);
x -= x & -x;
}
return ret;
}
void set(int x){
x++;
//cout << "set : " << x << "\n";
while(x < 202020){
tree[x] = 0;
x += x & -x;
}
}
}bit;
struct Node{
int x, y, z;
Node(int a, int b, int c) : x(a), y(b), z(c) {}
Node() : Node(0, 0, 0) {}
bool operator < (Node &rhs){
if(x != rhs.x) return x < rhs.x;
if(y != rhs.y) return y < rhs.y;
return z < rhs.z;
}
};
int n, m;
vector<Node> v;
int dp[202020];
void solve(int s, int e){
if(s == e){
dp[s]++; return;
}
int m = s + e >> 1;
//left
solve(s, m);
//propagation : [s, m] -> [m+1, e]
vector<Node> left, right;
for(int i=s; i<=m; i++) left.push_back({v[i].y, v[i].z, dp[i]});
for(int i=m+1; i<=e; i++) right.push_back({v[i].y, v[i].z, i});
sort(left.begin(), left.end());
sort(right.begin(), right.end());
int idx = 0;
for(auto i : right){
while(idx < left.size() && left[idx].x < i.x){
bit.update(left[idx].y, left[idx].z); idx++;
}
dp[i.z] = max(dp[i.z], bit.query(i.y-1));
}
for(int i=0; i<idx; i++) bit.set(v[i].y);
//right
solve(m+1, e);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> m >> n; v.resize(n+1);
for(int i=1; i<=n; i++) cin >> v[i].x;
for(int i=1; i<=n; i++) cin >> v[i].y;
if(m == 3) for(int i=1; i<=n; i++) cin >> v[i].z;
sort(v.begin()+1, v.end());
if(m == 2) for(int i=1; i<=n; i++) v[i].z = i;
//decompress
vector<int> yy, zz;
for(int i=1; i<=n; i++){
yy.push_back(v[i].y);
zz.push_back(v[i].z);
}
sort(all(yy));
sort(all(zz));
for(int i=1; i<=n; i++){
v[i].y = lower_bound(all(yy), v[i].y) - yy.begin();
v[i].z = lower_bound(all(zz), v[i].z) - zz.begin();
}
solve(1, n);
int ans = 0;
for(int i=1; i<=n; i++) ans = max(ans, dp[i]);
cout << ans;
}
Compilation message
matrix.cpp: In function 'void solve(int, int)':
matrix.cpp:58:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s + e >> 1;
~~^~~
matrix.cpp:72:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(idx < left.size() && left[idx].x < i.x){
~~~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
18 ms |
896 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
20 ms |
1024 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
18 ms |
896 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
20 ms |
1024 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |