#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
int n,m;
const int MX=2e5+5;
pair<int,pair<int,int>> a[MX];
unordered_map<long long,int> seg;
unordered_map<int,int> xx;
unordered_map<int,int> yy;
long long nn;
int ans;
int p;
stack<int> S;
inline int g(int y,int lev1){
S.push(1);
S.push(nn);
S.push(1);
int k=0;
while(!S.empty()){
int lv=S.top();S.pop();
int r=S.top();S.pop();
int l=S.top();S.pop();
if(l>=y)continue;
if(r<y)k=max(k,seg[nn*2*lev1+lv]);
else{
if(y>(l+r)/2+1){
k=max(k,seg[nn*2*lev1+lv*2]);
S.push((l+r)/2+1);
S.push(r);
S.push(lv*2+1);
}
else{
S.push(l);
S.push((l+r)/2);
S.push(lv*2);
}
}
}
return k;
}
inline int f(int x,int y){
S.push(1);
S.push(nn);
S.push(1);
int k=0;
while(!S.empty()){
int lv=S.top();S.pop();
int r=S.top();S.pop();
int l=S.top();S.pop();
if(l>=x)continue;
if(r<x)k=max(k,g(y,lv));
else{
if(x>(l+r)/2+1){
k=max(k,g(y,lv*2));
S.push((l+r)/2+1);
S.push(r);
S.push(lv*2+1);
}
else{
S.push(l);
S.push((l+r)/2);
S.push(lv*2);
}
}
}
return k;
}
void process(){
int i,j;
for(nn=1 ; nn<n ; nn*=2);
for(i=1 ; i<=n ; i++)cin>>a[i].f;
for(i=1 ; i<=n ; i++)cin>>a[i].s.f;
for(i=1 ; i<=n ; i++)cin>>a[i].s.s;
sort(a+1,a+n+1);
set<int> S1;
set<int> S2;
for(i=1 ; i<=n ; i++){
S1.insert(a[i].s.f);
S2.insert(a[i].s.s);
}
int cnt=0;
for(auto &i:S1)xx[i]=++cnt;
cnt=0;
for(auto &i:S2)yy[i]=++cnt;
for(int ii=1 ; ii<=n ; ii++){
int k;
if(n<=10000){
k=f(xx[a[ii].s.f],yy[a[ii].s.s])+1;
}
for(i=nn+xx[a[ii].s.f]-1 ; i>=1 ; i/=2){
if(n<=10000){
for(j=nn+yy[a[ii].s.s]-1 ; j>=1 ; j/=2)
if(seg[nn*2*i+j]<k)
seg[nn*2*i+j]=k;
else
break;
}
else
k=k*k*k*k*k;
}
ans=ans>k?ans:k;
}
cout<<ans;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>m>>n;
if(m==3)process();
return 0;
}
Compilation message
matrix.cpp: In function 'void process()':
matrix.cpp:98:34: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
seg[nn*2*i+j]=k;
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
248 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
691 ms |
34512 KB |
Output is correct |
2 |
Correct |
562 ms |
34512 KB |
Output is correct |
3 |
Correct |
1180 ms |
52340 KB |
Output is correct |
4 |
Correct |
1429 ms |
59840 KB |
Output is correct |
5 |
Correct |
938 ms |
59840 KB |
Output is correct |
6 |
Correct |
525 ms |
59840 KB |
Output is correct |
7 |
Correct |
1369 ms |
59840 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
248 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
691 ms |
34512 KB |
Output is correct |
2 |
Correct |
562 ms |
34512 KB |
Output is correct |
3 |
Correct |
1180 ms |
52340 KB |
Output is correct |
4 |
Correct |
1429 ms |
59840 KB |
Output is correct |
5 |
Correct |
938 ms |
59840 KB |
Output is correct |
6 |
Correct |
525 ms |
59840 KB |
Output is correct |
7 |
Correct |
1369 ms |
59840 KB |
Output is correct |
8 |
Incorrect |
590 ms |
59840 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |