# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
63351 |
2018-08-01T14:19:20 Z |
knon0501 |
None (KOI18_matrix) |
C++14 |
|
1283 ms |
47876 KB |
#include <bits/stdc++.h>
using namespace std;
#define mp(x,y) make_pair(x,y)
#define f first
#define s second
int n,m;
const int MX=2e5+5;
pair<int,pair<int,int>> a[MX];
unordered_map<int,int> xx;
unordered_map<int,int> yy;
map<pair<int,int>,int> idx;
int seg[MX*100];
int nn;
int ans;
int p;
int g(int y,int lef,int rig,int lev1,int lev2){
return 0;
if(rig<=y)return seg[idx[mp(lev1,lev2)]];
int mid=(lef+rig)/2;
int k=g(y,lef,mid,lev1,lev2*2);
if(y>mid+1)k=max(k,g(y,mid+1,rig,lev1,lev2*2+1));
return k;
}
int f(int x,int y,int lef,int rig,int lev){
return 0;
if(rig<=x)return g(y,1,nn,lev,1);
int mid=(lef+rig)/2;
int k=f(x,y,lef,mid,lev*2);
if(x>mid+1)k=max(k,f(x,y,mid+1,rig,lev*2+1));
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=f(xx[a[ii].s.f],yy[a[ii].s.s],1,nn,1)+1;
for(i=nn+xx[a[ii].s.f]-1 ; i>=1 ; i/=2){
for(j=nn+yy[a[ii].s.s]-1 ; j>=1 ; j/=2){
if(idx[mp(i,j)]==0)idx[mp(i,j)]=++p;
seg[idx[mp(i,j)]]=max(seg[idx[mp(i,j)]],k);
}
}
ans=max(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;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1283 ms |
47876 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1283 ms |
47876 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |