# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
65692 |
2018-08-08T12:07:02 Z |
knon0501 |
None (KOI18_matrix) |
C++17 |
|
4000 ms |
787456 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;
set<int> S1;
set<int> S2;
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;
else u=g(y,mid+1,r,seg[lv].rr);
}
if(seg[lv].ll==0)seg[lv].ll=++num;
else
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;
else u=f(x,y,mid+1,r,seg[lv].r);
}
if(seg[lv].l==0)seg[lv].l=++num;
else 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;
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=max(ans,k);
}
cout<<ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
40 ms |
7416 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
57 ms |
17948 KB |
Output is correct |
2 |
Correct |
58 ms |
17948 KB |
Output is correct |
3 |
Correct |
98 ms |
23608 KB |
Output is correct |
4 |
Correct |
134 ms |
27740 KB |
Output is correct |
5 |
Correct |
75 ms |
27740 KB |
Output is correct |
6 |
Correct |
54 ms |
27740 KB |
Output is correct |
7 |
Correct |
122 ms |
27740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
40 ms |
7416 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
57 ms |
17948 KB |
Output is correct |
2 |
Correct |
58 ms |
17948 KB |
Output is correct |
3 |
Correct |
98 ms |
23608 KB |
Output is correct |
4 |
Correct |
134 ms |
27740 KB |
Output is correct |
5 |
Correct |
75 ms |
27740 KB |
Output is correct |
6 |
Correct |
54 ms |
27740 KB |
Output is correct |
7 |
Correct |
122 ms |
27740 KB |
Output is correct |
8 |
Correct |
1857 ms |
467632 KB |
Output is correct |
9 |
Correct |
3962 ms |
607900 KB |
Output is correct |
10 |
Correct |
1646 ms |
607900 KB |
Output is correct |
11 |
Correct |
1553 ms |
607900 KB |
Output is correct |
12 |
Runtime error |
4000 ms |
787456 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
13 |
Halted |
0 ms |
0 KB |
- |