oj.uz

Submission #63338

# Submission time Handle Problem Language Result Execution time Memory
63338 2018-08-01T13:43:34 Z knon0501 None (KOI18_matrix) C++14
9 / 100
 4000 ms 172580 KB 
#include <bits/stdc++.h>
using namespace std;

#define mp(x,y) make_pair(x,y)
#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;

map<pair<int,int>,int> idx;
int seg[MX*100];
int nn;
int ans;
int p;
int g(int y,int lef,int rig,int lev1,int lev2){
    if(rig<=y)return seg[idx[mp(lev1,lev2)]];
    if(lef>y)return 0;
    int mid=(lef+rig)/2;
    return max(g(y,lef,mid,lev1,lev2*2),g(y,mid+1,rig,lev1,lev2*2+1));
}
int f(int x,int y,int lef,int rig,int lev){
    if(lef>x)return 0;
    if(rig<=x)return g(y,1,nn,lev,1);
    int mid=(lef+rig)/2;
    return max(f(x,y,lef,mid,lev*2),f(x,y,mid+1,rig,lev*2+1));
}
void process(){
    int i,j;
    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);
    set<int> S1;
    set<int> S2;
    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;
    }

    for(int ii=1 ; ii<=n ; ii++){
        int k=f(xx[a[ii].s.f],yy[a[ii].s.s],1,nn,1)+1;
        for(i=nn+xx[a[ii].s.f]-1 ; i>=1 ; i/=2){
            for(j=nn+yy[a[ii].s.s]-1 ; j>=1 ; j/=2){
                if(idx[mp(i,j)]==0)
                    idx[mp(i,j)]=++p;
                seg[idx[mp(i,j)]]=max(seg[idx[mp(i,j)]],k);
            }
        }
        ans=max(ans,k);
    }
    cout<<ans;
}

int main(){

    cin>>m>>n;
    if(m==3){
        process();
    }
    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 252 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 1372 ms 55224 KB Output is correct
2 Correct 1340 ms 55224 KB Output is correct
3 Correct 1954 ms 77844 KB Output is correct
4 Correct 2507 ms 94028 KB Output is correct
5 Correct 1436 ms 94028 KB Output is correct
6 Correct 1268 ms 94028 KB Output is correct
7 Correct 2262 ms 94028 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 1372 ms 55224 KB Output is correct
2 Correct 1340 ms 55224 KB Output is correct
3 Correct 1954 ms 77844 KB Output is correct
4 Correct 2507 ms 94028 KB Output is correct
5 Correct 1436 ms 94028 KB Output is correct
6 Correct 1268 ms 94028 KB Output is correct
7 Correct 2262 ms 94028 KB Output is correct
8 Execution timed out 4054 ms 172580 KB Time limit exceeded
9 Halted 0 ms 0 KB -