# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
65685 |
2018-08-08T12:00:16 Z |
knon0501 |
None (KOI18_matrix) |
C++14 |
|
4000 ms |
764292 KB |
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
int n,m;
const int MX=2e5+5;
#define mp(x,y) make_pair(x,y)
pair<int,pair<int,int>> a[MX];
map<int,int> xx;
map<int,int> yy;
long long nn;
int ans;
int p;
int num;
set<int> S1;
set<int> S2;
stack<int> S;
set<pair<int,int>> chk;
struct Tree{
int l,r,ll,rr,d;
}seg[MX*400];
int g(int y,int l,int r,int lv){
if(l>=y)return 0;
if(r<y)return seg[lv].d;
int u=0,v=0;
int mid=(l+r)/2;
if(y>mid){
if(seg[lv].rr==0)seg[lv].rr=++num;
u=g(y,mid+1,r,seg[lv].rr);
}
if(seg[lv].ll==0)seg[lv].ll=++num;
v=g(y,l,mid,seg[lv].ll);
return max(u,v);
}
int f(int x,int y,int l,int r,int lv){
if(l>=x)return 0;
if(r<x)return g(y,1,nn,lv);
int u=0,v=0;
int mid=(l+r)/2;
if(x>mid){
if(seg[lv].r==0)seg[lv].r=++num;
u=f(x,y,mid+1,r,seg[lv].r);
}
if(seg[lv].l==0)seg[lv].l=++num;
v=f(x,y,l,mid,seg[lv].l);
return max(u,v);
}
void update2(int y,int l,int r,int lv,int k){
seg[lv].d=max(seg[lv].d,k);
int mid=(l+r)/2;
if(l==r)return;
if(y>mid){
if(seg[lv].rr==0)seg[lv].rr=++num;
update2(y,mid+1,r,seg[lv].rr,k);
}
else{
if(seg[lv].ll==0)seg[lv].ll=++num;
update2(y,l,mid,seg[lv].ll,k);
}
}
void update(int x,int y,int l,int r,int lv,int k){
seg[lv].d=max(seg[lv].d,k);
int mid=(l+r)/2;
if(l!=r){
if(x>mid){
if(seg[lv].r==0)seg[lv].r=++num;
update(x,y,mid+1,r,seg[lv].r,k);
}
else{
if(seg[lv].l==0)seg[lv].l=++num;
update(x,y,l,mid,seg[lv].l,k);
}
}
update2(y,1,nn,lv,k);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>m>>n;
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);
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;
int tx,ty,k;
chk.insert(mp(1,1));
++num;
for(int ii=1 ; ii<=n ; ii++){
tx=xx[a[ii].s.f];
ty=yy[a[ii].s.s];
k=f(tx,ty,1,nn,1)+1;
update(tx,ty,1,nn,1,k);
ans=ans>k?ans:k;
}
cout<<ans;
return 0;
}
Compilation message
matrix.cpp: In function 'int main()':
matrix.cpp:86:11: warning: unused variable 'j' [-Wunused-variable]
int i,j;
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
56 ms |
7416 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
67 ms |
21024 KB |
Output is correct |
2 |
Correct |
60 ms |
21024 KB |
Output is correct |
3 |
Correct |
110 ms |
30724 KB |
Output is correct |
4 |
Correct |
183 ms |
37772 KB |
Output is correct |
5 |
Correct |
95 ms |
37772 KB |
Output is correct |
6 |
Correct |
57 ms |
37772 KB |
Output is correct |
7 |
Correct |
166 ms |
37772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
56 ms |
7416 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
67 ms |
21024 KB |
Output is correct |
2 |
Correct |
60 ms |
21024 KB |
Output is correct |
3 |
Correct |
110 ms |
30724 KB |
Output is correct |
4 |
Correct |
183 ms |
37772 KB |
Output is correct |
5 |
Correct |
95 ms |
37772 KB |
Output is correct |
6 |
Correct |
57 ms |
37772 KB |
Output is correct |
7 |
Correct |
166 ms |
37772 KB |
Output is correct |
8 |
Correct |
2514 ms |
574648 KB |
Output is correct |
9 |
Execution timed out |
4061 ms |
764292 KB |
Time limit exceeded |
10 |
Halted |
0 ms |
0 KB |
- |