oj.uz

Submission #65703

# Submission time Handle Problem Language Result Execution time Memory
65703 2018-08-08T12:36:54 Z knon0501 None (KOI18_matrix) C++14
38 / 100
 4000 ms 500040 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;
long long nn;
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*600];

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,nn,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,nn,seg[lv].w,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=max2(ans,k);
    }


    cout<<ans;
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 5116 KB Output is correct
2 Correct 37 ms 5352 KB Output is correct
3 Correct 37 ms 5492 KB Output is correct
4 Correct 35 ms 5932 KB Output is correct
5 Correct 53 ms 6068 KB Output is correct
6 Correct 38 ms 6380 KB Output is correct
7 Correct 36 ms 6432 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 11804 KB Output is correct
2 Correct 51 ms 11804 KB Output is correct
3 Correct 83 ms 15212 KB Output is correct
4 Correct 108 ms 17620 KB Output is correct
5 Correct 61 ms 17620 KB Output is correct
6 Correct 47 ms 17620 KB Output is correct
7 Correct 90 ms 17620 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 5116 KB Output is correct
2 Correct 37 ms 5352 KB Output is correct
3 Correct 37 ms 5492 KB Output is correct
4 Correct 35 ms 5932 KB Output is correct
5 Correct 53 ms 6068 KB Output is correct
6 Correct 38 ms 6380 KB Output is correct
7 Correct 36 ms 6432 KB Output is correct
8 Correct 1924 ms 119384 KB Output is correct
9 Correct 1794 ms 123360 KB Output is correct
10 Correct 1100 ms 127068 KB Output is correct
11 Correct 956 ms 127248 KB Output is correct
12 Correct 1507 ms 127248 KB Output is correct
13 Correct 1167 ms 127248 KB Output is correct
14 Correct 1195 ms 127304 KB Output is correct
15 Correct 833 ms 127304 KB Output is correct
16 Correct 1067 ms 127340 KB Output is correct
17 Correct 1109 ms 127340 KB Output is correct
18 Correct 1132 ms 127340 KB Output is correct
19 Correct 1080 ms 127340 KB Output is correct
20 Correct 1814 ms 127340 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 11804 KB Output is correct
2 Correct 51 ms 11804 KB Output is correct
3 Correct 83 ms 15212 KB Output is correct
4 Correct 108 ms 17620 KB Output is correct
5 Correct 61 ms 17620 KB Output is correct
6 Correct 47 ms 17620 KB Output is correct
7 Correct 90 ms 17620 KB Output is correct
8 Correct 1554 ms 281852 KB Output is correct
9 Correct 2563 ms 370952 KB Output is correct
10 Correct 1457 ms 370952 KB Output is correct
11 Correct 1370 ms 370952 KB Output is correct
12 Correct 2394 ms 500040 KB Output is correct
13 Correct 1488 ms 500040 KB Output is correct
14 Correct 2855 ms 500040 KB Output is correct
15 Correct 1300 ms 500040 KB Output is correct
16 Correct 1288 ms 500040 KB Output is correct
17 Correct 2671 ms 500040 KB Output is correct
18 Execution timed out 4091 ms 500040 KB Time limit exceeded
19 Halted 0 ms 0 KB -