# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
65701 |
2018-08-08T12:28:46 Z |
knon0501 |
None (KOI18_matrix) |
C++17 |
|
4000 ms |
489668 KB |
#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];
map<int,int> xx;
map<int,int> yy;
long long nn;
int ans;
int num;
int num2;
set<int> S1;
set<int> S2;
struct Tree{
int l,r,w;
}seg[MX*40];
struct Real{
int l,r,d;
}seg2[MX*600];
inline int max2(int x,int y){
return x>y ?x:y;
}
int g(int y,int l,int r,int lv){
if(l>=y)return 0;
if(r<y)return seg2[lv].d;
int u=0,v=0;
int mid=(l+r)/2;
if(y>mid){
if(seg2[lv].r!=0)u=g(y,mid+1,r,seg2[lv].r);
}
if(seg2[lv].l!=0) v=g(y,l,mid,seg2[lv].l);
return max2(u,v);
}
int f(int x,int y,int l,int r,int lv){
if(l>=x)return 0;
if(r<x){
if(seg[lv].w==0)return 0;
return g(y,1,nn,seg[lv].w);
}
int u=0,v=0;
int mid=(l+r)/2;
if(x>mid){
if(seg[lv].r!=0)u=f(x,y,mid+1,r,seg[lv].r);
}
if(seg[lv].l!=0)v=f(x,y,l,mid,seg[lv].l);
return max2(u,v);
}
void update2(int y,int l,int r,int lv,int k){
seg2[lv].d=max2(seg2[lv].d,k);
int mid=(l+r)/2;
if(l==r)return;
if(y>mid){
if(seg2[lv].r==0)seg2[lv].r=++num2;
update2(y,mid+1,r,seg2[lv].r,k);
}
else{
if(seg2[lv].l==0)seg2[lv].l=++num2;
update2(y,l,mid,seg2[lv].l,k);
}
}
void update(int x,int y,int l,int r,int lv,int 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);
}
}
if(seg[lv].w==0)seg[lv].w=++num2;
update2(y,1,nn,seg[lv].w,k);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>m>>n;
int i;
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;
++num;
for(i=1 ; i<=n ; i++){
tx=xx[a[i].s.f];
ty=yy[a[i].s.s];
k=f(tx,ty,1,nn,1)+1;
update(tx,ty,1,nn,1,k);
ans=max2(ans,k);
}
cout<<ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
38 ms |
5240 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
55 ms |
10728 KB |
Output is correct |
2 |
Correct |
52 ms |
10728 KB |
Output is correct |
3 |
Correct |
69 ms |
14032 KB |
Output is correct |
4 |
Correct |
103 ms |
16392 KB |
Output is correct |
5 |
Correct |
53 ms |
16392 KB |
Output is correct |
6 |
Correct |
44 ms |
16392 KB |
Output is correct |
7 |
Correct |
90 ms |
16392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
38 ms |
5240 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
55 ms |
10728 KB |
Output is correct |
2 |
Correct |
52 ms |
10728 KB |
Output is correct |
3 |
Correct |
69 ms |
14032 KB |
Output is correct |
4 |
Correct |
103 ms |
16392 KB |
Output is correct |
5 |
Correct |
53 ms |
16392 KB |
Output is correct |
6 |
Correct |
44 ms |
16392 KB |
Output is correct |
7 |
Correct |
90 ms |
16392 KB |
Output is correct |
8 |
Correct |
1494 ms |
271828 KB |
Output is correct |
9 |
Correct |
2837 ms |
360936 KB |
Output is correct |
10 |
Correct |
1236 ms |
360936 KB |
Output is correct |
11 |
Correct |
1253 ms |
360936 KB |
Output is correct |
12 |
Correct |
2614 ms |
489668 KB |
Output is correct |
13 |
Correct |
1380 ms |
489668 KB |
Output is correct |
14 |
Correct |
2929 ms |
489668 KB |
Output is correct |
15 |
Correct |
1246 ms |
489668 KB |
Output is correct |
16 |
Correct |
1296 ms |
489668 KB |
Output is correct |
17 |
Correct |
2667 ms |
489668 KB |
Output is correct |
18 |
Execution timed out |
4070 ms |
489668 KB |
Time limit exceeded |
19 |
Halted |
0 ms |
0 KB |
- |