oj.uz

Submission #67530

# Submission time Handle Problem Language Result Execution time Memory
67530 2018-08-14T16:54:51 Z knon0501 None (KOI18_matrix) C++14
38 / 100
 4000 ms 486984 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*200];
 
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 37 ms 5112 KB Output is correct
2 Correct 33 ms 5112 KB Output is correct
3 Correct 33 ms 5156 KB Output is correct
4 Correct 31 ms 5460 KB Output is correct
5 Correct 37 ms 5460 KB Output is correct
6 Correct 27 ms 5460 KB Output is correct
7 Correct 31 ms 5460 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 10428 KB Output is correct
2 Correct 42 ms 10428 KB Output is correct
3 Correct 63 ms 13752 KB Output is correct
4 Correct 94 ms 16184 KB Output is correct
5 Correct 52 ms 16184 KB Output is correct
6 Correct 40 ms 16184 KB Output is correct
7 Correct 94 ms 16184 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 5112 KB Output is correct
2 Correct 33 ms 5112 KB Output is correct
3 Correct 33 ms 5156 KB Output is correct
4 Correct 31 ms 5460 KB Output is correct
5 Correct 37 ms 5460 KB Output is correct
6 Correct 27 ms 5460 KB Output is correct
7 Correct 31 ms 5460 KB Output is correct
8 Correct 1787 ms 114356 KB Output is correct
9 Correct 1697 ms 114436 KB Output is correct
10 Correct 1072 ms 114436 KB Output is correct
11 Correct 914 ms 114476 KB Output is correct
12 Correct 1495 ms 114476 KB Output is correct
13 Correct 1002 ms 114476 KB Output is correct
14 Correct 1198 ms 114476 KB Output is correct
15 Correct 874 ms 114476 KB Output is correct
16 Correct 837 ms 114476 KB Output is correct
17 Correct 952 ms 114476 KB Output is correct
18 Correct 962 ms 114476 KB Output is correct
19 Correct 1071 ms 114476 KB Output is correct
20 Correct 1999 ms 114476 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 10428 KB Output is correct
2 Correct 42 ms 10428 KB Output is correct
3 Correct 63 ms 13752 KB Output is correct
4 Correct 94 ms 16184 KB Output is correct
5 Correct 52 ms 16184 KB Output is correct
6 Correct 40 ms 16184 KB Output is correct
7 Correct 94 ms 16184 KB Output is correct
8 Correct 1584 ms 268200 KB Output is correct
9 Correct 2302 ms 360924 KB Output is correct
10 Correct 1303 ms 360924 KB Output is correct
11 Correct 1113 ms 360924 KB Output is correct
12 Correct 2329 ms 486984 KB Output is correct
13 Correct 1440 ms 486984 KB Output is correct
14 Correct 2555 ms 486984 KB Output is correct
15 Correct 1314 ms 486984 KB Output is correct
16 Correct 1298 ms 486984 KB Output is correct
17 Correct 2423 ms 486984 KB Output is correct
18 Execution timed out 4048 ms 486984 KB Time limit exceeded
19 Halted 0 ms 0 KB -