oj.uz

Submission #65711

# Submission time Handle Problem Language Result Execution time Memory
65711 2018-08-08T12:54:25 Z knon0501 None (KOI18_matrix) C++17
38 / 100
 4000 ms 486972 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];

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(u==ans)return u;
    }
    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(u==ans)return u;
    }
    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);
        if(ans==n)break;
    }


    cout<<ans;
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5112 KB Output is correct
2 Correct 32 ms 5220 KB Output is correct
3 Correct 35 ms 5296 KB Output is correct
4 Correct 33 ms 5296 KB Output is correct
5 Correct 40 ms 5332 KB Output is correct
6 Correct 26 ms 5332 KB Output is correct
7 Correct 30 ms 5332 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 10440 KB Output is correct
2 Correct 43 ms 10440 KB Output is correct
3 Correct 61 ms 13768 KB Output is correct
4 Correct 107 ms 16200 KB Output is correct
5 Correct 59 ms 16200 KB Output is correct
6 Correct 39 ms 16200 KB Output is correct
7 Correct 92 ms 16200 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5112 KB Output is correct
2 Correct 32 ms 5220 KB Output is correct
3 Correct 35 ms 5296 KB Output is correct
4 Correct 33 ms 5296 KB Output is correct
5 Correct 40 ms 5332 KB Output is correct
6 Correct 26 ms 5332 KB Output is correct
7 Correct 30 ms 5332 KB Output is correct
8 Correct 1821 ms 114332 KB Output is correct
9 Correct 1408 ms 114352 KB Output is correct
10 Correct 967 ms 114372 KB Output is correct
11 Correct 849 ms 114420 KB Output is correct
12 Correct 1336 ms 114420 KB Output is correct
13 Correct 1040 ms 114420 KB Output is correct
14 Correct 1117 ms 114420 KB Output is correct
15 Correct 857 ms 114472 KB Output is correct
16 Correct 886 ms 114472 KB Output is correct
17 Correct 929 ms 114492 KB Output is correct
18 Correct 912 ms 114492 KB Output is correct
19 Correct 990 ms 114492 KB Output is correct
20 Correct 1859 ms 114492 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 10440 KB Output is correct
2 Correct 43 ms 10440 KB Output is correct
3 Correct 61 ms 13768 KB Output is correct
4 Correct 107 ms 16200 KB Output is correct
5 Correct 59 ms 16200 KB Output is correct
6 Correct 39 ms 16200 KB Output is correct
7 Correct 92 ms 16200 KB Output is correct
8 Correct 1551 ms 268280 KB Output is correct
9 Correct 2590 ms 360908 KB Output is correct
10 Correct 1418 ms 360908 KB Output is correct
11 Correct 1282 ms 360908 KB Output is correct
12 Correct 2362 ms 486972 KB Output is correct
13 Correct 1426 ms 486972 KB Output is correct
14 Correct 2707 ms 486972 KB Output is correct
15 Correct 1303 ms 486972 KB Output is correct
16 Correct 1298 ms 486972 KB Output is correct
17 Correct 2334 ms 486972 KB Output is correct
18 Execution timed out 4065 ms 486972 KB Time limit exceeded
19 Halted 0 ms 0 KB -