oj.uz

Submission #65709

# Submission time Handle Problem Language Result Execution time Memory
65709 2018-08-08T12:49:45 Z knon0501 None (KOI18_matrix) C++17
38 / 100
 4000 ms 486816 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*3];
struct Real{
    int l,r,d;
}seg2[MX*700];
int u,v;
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;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 5112 KB Output is correct
2 Correct 41 ms 5228 KB Output is correct
3 Correct 39 ms 5228 KB Output is correct
4 Correct 34 ms 5228 KB Output is correct
5 Correct 52 ms 5252 KB Output is correct
6 Correct 34 ms 5252 KB Output is correct
7 Correct 32 ms 5380 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 10404 KB Output is correct
2 Correct 48 ms 10404 KB Output is correct
3 Correct 85 ms 13776 KB Output is correct
4 Correct 97 ms 16084 KB Output is correct
5 Correct 58 ms 16084 KB Output is correct
6 Correct 45 ms 16084 KB Output is correct
7 Correct 91 ms 16084 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 5112 KB Output is correct
2 Correct 41 ms 5228 KB Output is correct
3 Correct 39 ms 5228 KB Output is correct
4 Correct 34 ms 5228 KB Output is correct
5 Correct 52 ms 5252 KB Output is correct
6 Correct 34 ms 5252 KB Output is correct
7 Correct 32 ms 5380 KB Output is correct
8 Correct 1848 ms 114176 KB Output is correct
9 Correct 1688 ms 114264 KB Output is correct
10 Correct 1092 ms 114264 KB Output is correct
11 Correct 785 ms 114264 KB Output is correct
12 Correct 1254 ms 114284 KB Output is correct
13 Correct 1112 ms 114284 KB Output is correct
14 Correct 1094 ms 114284 KB Output is correct
15 Correct 807 ms 114312 KB Output is correct
16 Correct 1066 ms 114312 KB Output is correct
17 Correct 1117 ms 114484 KB Output is correct
18 Correct 1062 ms 114484 KB Output is correct
19 Correct 1064 ms 114484 KB Output is correct
20 Correct 1776 ms 114484 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 10404 KB Output is correct
2 Correct 48 ms 10404 KB Output is correct
3 Correct 85 ms 13776 KB Output is correct
4 Correct 97 ms 16084 KB Output is correct
5 Correct 58 ms 16084 KB Output is correct
6 Correct 45 ms 16084 KB Output is correct
7 Correct 91 ms 16084 KB Output is correct
8 Correct 1639 ms 268132 KB Output is correct
9 Correct 2425 ms 360988 KB Output is correct
10 Correct 1507 ms 360988 KB Output is correct
11 Correct 1244 ms 360988 KB Output is correct
12 Correct 2822 ms 486816 KB Output is correct
13 Correct 1480 ms 486816 KB Output is correct
14 Correct 3017 ms 486816 KB Output is correct
15 Correct 1396 ms 486816 KB Output is correct
16 Correct 1422 ms 486816 KB Output is correct
17 Correct 2367 ms 486816 KB Output is correct
18 Execution timed out 4050 ms 486816 KB Time limit exceeded
19 Halted 0 ms 0 KB -