oj.uz

Submission #65700

# Submission time Handle Problem Language Result Execution time Memory
65700 2018-08-08T12:25:36 Z knon0501 None (KOI18_matrix) C++14
9 / 100
 4000 ms 493316 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;
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];
int g(int y,int l,int r,int lv){
    if(l>=y)return 0;
    if(r<y)return seg2[lv].d;
    int u=0,v=0;
    int mid=(l+r)/2;
    if(y>mid){
        if(seg2[lv].r!=0)u=g(y,mid+1,r,seg2[lv].r);
    }
    if(seg2[lv].l!=0) v=g(y,l,mid,seg2[lv].l);
    return max(u,v);
}
int f(int x,int y,int l,int r,int lv){
    if(l>=x)return 0;
    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!=0)u=f(x,y,mid+1,r,seg[lv].r);
    }
    if(seg[lv].l!=0)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){
    seg2[lv].d=max(seg2[lv].d,k);
    int mid=(l+r)/2;
    if(l==r)return;
    if(y>mid){
        if(seg2[lv].r==0)seg2[lv].r=++num2;
        update2(y,mid+1,r,seg2[lv].r,k);
    }
    else{
        if(seg2[lv].l==0)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==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);
        }
    }
    if(seg[lv].w==0)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=max(ans,k);
    }


    cout<<ans;
    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 5368 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 70 ms 11036 KB Output is correct
2 Correct 51 ms 11036 KB Output is correct
3 Correct 82 ms 14980 KB Output is correct
4 Correct 109 ms 17816 KB Output is correct
5 Correct 61 ms 17816 KB Output is correct
6 Correct 50 ms 17816 KB Output is correct
7 Correct 109 ms 18052 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 11036 KB Output is correct
2 Correct 51 ms 11036 KB Output is correct
3 Correct 82 ms 14980 KB Output is correct
4 Correct 109 ms 17816 KB Output is correct
5 Correct 61 ms 17816 KB Output is correct
6 Correct 50 ms 17816 KB Output is correct
7 Correct 109 ms 18052 KB Output is correct
8 Correct 1491 ms 275060 KB Output is correct
9 Correct 2716 ms 364416 KB Output is correct
10 Correct 1276 ms 364416 KB Output is correct
11 Correct 1263 ms 364416 KB Output is correct
12 Correct 2822 ms 493316 KB Output is correct
13 Correct 1399 ms 493316 KB Output is correct
14 Correct 2945 ms 493316 KB Output is correct
15 Correct 1253 ms 493316 KB Output is correct
16 Correct 1205 ms 493316 KB Output is correct
17 Correct 2613 ms 493316 KB Output is correct
18 Execution timed out 4035 ms 493316 KB Time limit exceeded
19 Halted 0 ms 0 KB -