# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
65706 |
2018-08-08T12:43:59 Z |
knon0501 |
None (KOI18_matrix) |
C++17 |
|
4000 ms |
487096 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];
unordered_map<int,int> xx;
unordered_map<int,int> yy;
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*400];
inline int max2(int x,int y){
return x>y ?x:y;
}
int g(int y,int l,int r,int lv){
if(r<=y)return seg2[lv].d;
int u=0,v=0;
int mid=(l+r)/2;
if(y>mid){
if(seg2[lv].r)u=g(y,mid+1,r,seg2[lv].r);
}
if(seg2[lv].l) 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(r<=x){
if(seg[lv].w==0)return 0;
return g(y,1,n,seg[lv].w);
}
int u=0,v=0;
int mid=(l+r)/2;
if(x>mid){
if(seg[lv].r)u=f(x,y,mid+1,r,seg[lv].r);
}
if(seg[lv].l)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)seg2[lv].r=++num2;
update2(y,mid+1,r,seg2[lv].r,k);
}
else{
if(!seg2[lv].l)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)seg[lv].r=++num;
update(x,y,mid+1,r,seg[lv].r,k);
}
else{
if(!seg[lv].l)seg[lv].l=++num;
update(x,y,l,mid,seg[lv].l,k);
}
}
if(!seg[lv].w)seg[lv].w=++num2;
update2(y,1,n,seg[lv].w,k);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>m>>n;
int i;
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,n,1)+1;
update(tx,ty,1,n,1,k);
ans=max2(ans,k);
}
cout<<ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
5112 KB |
Output is correct |
2 |
Correct |
36 ms |
5112 KB |
Output is correct |
3 |
Correct |
42 ms |
5260 KB |
Output is correct |
4 |
Correct |
40 ms |
5260 KB |
Output is correct |
5 |
Correct |
44 ms |
5260 KB |
Output is correct |
6 |
Correct |
38 ms |
5260 KB |
Output is correct |
7 |
Correct |
34 ms |
5356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
55 ms |
10356 KB |
Output is correct |
2 |
Correct |
51 ms |
10356 KB |
Output is correct |
3 |
Correct |
67 ms |
13816 KB |
Output is correct |
4 |
Correct |
97 ms |
16132 KB |
Output is correct |
5 |
Correct |
66 ms |
16132 KB |
Output is correct |
6 |
Correct |
51 ms |
16132 KB |
Output is correct |
7 |
Correct |
103 ms |
16132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
5112 KB |
Output is correct |
2 |
Correct |
36 ms |
5112 KB |
Output is correct |
3 |
Correct |
42 ms |
5260 KB |
Output is correct |
4 |
Correct |
40 ms |
5260 KB |
Output is correct |
5 |
Correct |
44 ms |
5260 KB |
Output is correct |
6 |
Correct |
38 ms |
5260 KB |
Output is correct |
7 |
Correct |
34 ms |
5356 KB |
Output is correct |
8 |
Correct |
2004 ms |
114264 KB |
Output is correct |
9 |
Correct |
1732 ms |
114264 KB |
Output is correct |
10 |
Correct |
1050 ms |
114264 KB |
Output is correct |
11 |
Correct |
804 ms |
114396 KB |
Output is correct |
12 |
Correct |
1357 ms |
114452 KB |
Output is correct |
13 |
Correct |
1143 ms |
114452 KB |
Output is correct |
14 |
Correct |
1149 ms |
114452 KB |
Output is correct |
15 |
Correct |
894 ms |
114452 KB |
Output is correct |
16 |
Correct |
1099 ms |
114452 KB |
Output is correct |
17 |
Correct |
1025 ms |
114452 KB |
Output is correct |
18 |
Correct |
1110 ms |
114452 KB |
Output is correct |
19 |
Correct |
1117 ms |
114452 KB |
Output is correct |
20 |
Correct |
2082 ms |
114492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
55 ms |
10356 KB |
Output is correct |
2 |
Correct |
51 ms |
10356 KB |
Output is correct |
3 |
Correct |
67 ms |
13816 KB |
Output is correct |
4 |
Correct |
97 ms |
16132 KB |
Output is correct |
5 |
Correct |
66 ms |
16132 KB |
Output is correct |
6 |
Correct |
51 ms |
16132 KB |
Output is correct |
7 |
Correct |
103 ms |
16132 KB |
Output is correct |
8 |
Correct |
1570 ms |
268144 KB |
Output is correct |
9 |
Correct |
2377 ms |
360892 KB |
Output is correct |
10 |
Correct |
1384 ms |
360892 KB |
Output is correct |
11 |
Correct |
1319 ms |
360892 KB |
Output is correct |
12 |
Correct |
2530 ms |
487096 KB |
Output is correct |
13 |
Correct |
1524 ms |
487096 KB |
Output is correct |
14 |
Correct |
2840 ms |
487096 KB |
Output is correct |
15 |
Correct |
1312 ms |
487096 KB |
Output is correct |
16 |
Correct |
1508 ms |
487096 KB |
Output is correct |
17 |
Correct |
2568 ms |
487096 KB |
Output is correct |
18 |
Execution timed out |
4067 ms |
487096 KB |
Time limit exceeded |
19 |
Halted |
0 ms |
0 KB |
- |