oj.uz

Submission #65691

# Submission time Handle Problem Language Result Execution time Memory
65691 2018-08-08T12:06:27 Z knon0501 None (KOI18_matrix) C++14
9 / 100
 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;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 7416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 17944 KB Output is correct
2 Correct 57 ms 17944 KB Output is correct
3 Correct 86 ms 23756 KB Output is correct
4 Correct 121 ms 27912 KB Output is correct
5 Correct 65 ms 27912 KB Output is correct
6 Correct 51 ms 27912 KB Output is correct
7 Correct 141 ms 27912 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 7416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 17944 KB Output is correct
2 Correct 57 ms 17944 KB Output is correct
3 Correct 86 ms 23756 KB Output is correct
4 Correct 121 ms 27912 KB Output is correct
5 Correct 65 ms 27912 KB Output is correct
6 Correct 51 ms 27912 KB Output is correct
7 Correct 141 ms 27912 KB Output is correct
8 Correct 1742 ms 467652 KB Output is correct
9 Correct 3448 ms 608000 KB Output is correct
10 Correct 1571 ms 608000 KB Output is correct
11 Correct 1538 ms 608000 KB Output is correct
12 Execution timed out 4030 ms 787456 KB Time limit exceeded
13 Halted 0 ms 0 KB -