oj.uz

Submission #65706

# Submission time Handle Problem Language Result Execution time Memory
65706 2018-08-08T12:43:59 Z knon0501 None (KOI18_matrix) C++17
38 / 100
 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;
}

Subtask #1
14.0 / 14.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

Subtask #2
9.0 / 9.0

# 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

Subtask #3
15.0 / 15.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
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

Subtask #4
0 / 62.0

# 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 -