oj.uz

Submission #423333

# Submission time Handle Problem Language Result Execution time Memory
423333 2021-06-11T01:54:56 Z ansol4328 None (KOI18_matrix) C++14
23 / 100
 457 ms 193464 KB 
#include<bits/stdc++.h>
#define pb push_back

using namespace std;

struct fenwick{
    vector<int> maxv; int sz;
    fenwick(int a){
        maxv.resize(a+5); sz=a;
    }
    void updt(int i, int v){
        for( ; i<=sz ; i+=i&-i) maxv[i]=max(maxv[i],v);
    }
    int qry(int i){
        int ret=0;
        for( ; i ; i-=i&-i) ret=max(maxv[i],ret);
        return ret;
    }
};

struct MGT{
    vector<vector<int>> tree;
    int base;
    MGT(int a, int arr[]){
        base=1;
        while(base<a) base<<=1;
        tree.resize(base*2+5);
        base--;
        for(int i=1 ; i<=a ; i++) tree[base+i].pb(arr[i]);
        setup();
    }
    void mg(vector<int> &cur, int i){
        vector<int> &L=tree[i*2];
        vector<int> &R=tree[i*2+1];
        int i1=0, i2=0, sz1=L.size(), sz2=R.size();
        while(i1<sz1 && i2<sz2){
            if(L[i1]<R[i2]) cur.pb(L[i1++]);
            else if(L[i1]>R[i2]) cur.pb(R[i2++]);
            else cur.pb(L[i1++]), cur.pb(R[i2++]);
        }
        while(i1<sz1) cur.pb(L[i1++]);
        while(i2<sz2) cur.pb(R[i2++]);
    }
    void setup(){
        for(int i=base ; i>=1 ; i--) mg(tree[i],i);
    }
    int get_idx(int i, int v){
        return lower_bound(tree[i].begin(),tree[i].end(),v)-tree[i].begin();
    }
};

struct A{
    int v[3];
    bool operator<(const A &rhs){
        return v[0]<rhs.v[0];
    }
};

int N;
A m[200005];
fenwick *seg[200005];
int bs, tmp[200005];

void cont(int i)
{
    vector<int> x;
    for(int j=1 ; j<=N ; j++) x.pb(m[j].v[i]);
    sort(x.begin(),x.end());
    for(int j=1 ; j<=N ; j++) m[j].v[i]=lower_bound(x.begin(),x.end(),m[j].v[i])-x.begin()+1;
}

int get_val(int fn, int v, MGT &mgt)
{
    int st=bs+1, ret=0; fn+=bs;
    while(st<fn){
        if(st&1){
            ret=max(ret,seg[st]->qry(mgt.get_idx(st,v))+1);
            st++;
        }
        if(~fn&1){
            ret=max(ret,seg[fn]->qry(mgt.get_idx(fn,v))+1);
            fn--;
        }
        st>>=1, fn>>=1;
    }
    if(st==fn) ret=max(ret,seg[st]->qry(mgt.get_idx(st,v))+1);
    return ret;
}

void update(int i, int f, int v, MGT &mgt)
{
    for(i+=bs ; i>=1 ; i>>=1){
        seg[i]->updt(mgt.get_idx(i,f)+1,v);
    }
}

int main()
{
    int r;
    scanf("%d %d",&r,&N);
    for(int i=0 ; i<r ; i++){
        for(int j=1 ; j<=N ; j++) scanf("%d",&m[j].v[i]);
        cont(i);
    }
    if(r==2) for(int i=1 ; i<=N ; i++) m[i].v[r]=m[i].v[r-1];
    
    sort(m+1,m+1+N);
    for(int i=1 ; i<=N ; i++) tmp[m[i].v[1]]=m[i].v[2];
    MGT mgt(N,tmp); bs=mgt.base;
    for(int i=1 ; i<=N+bs ; i++) seg[i]=new fenwick(mgt.tree[i].size());
    
    int ans=0;
    for(int i=1 ; i<=N ; i++){
        int val=get_val(m[i].v[1],m[i]
        .v[2],mgt);
        ans=max(ans,val);
        update(m[i].v[1],m[i].v[2],val,mgt);
    }
    printf("%d",ans);
    return 0;
}

Compilation message

matrix.cpp: In function 'int main()':
matrix.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |     scanf("%d %d",&r,&N);
      |     ~~~~~^~~~~~~~~~~~~~~
matrix.cpp:102:40: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         for(int j=1 ; j<=N ; j++) scanf("%d",&m[j].v[i]);
      |                                   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 5324 KB Output is correct
2 Correct 29 ms 5288 KB Output is correct
3 Correct 29 ms 5376 KB Output is correct
4 Correct 24 ms 5316 KB Output is correct
5 Correct 32 ms 5268 KB Output is correct
6 Correct 23 ms 5380 KB Output is correct
7 Correct 23 ms 5324 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5452 KB Output is correct
2 Correct 29 ms 5464 KB Output is correct
3 Correct 34 ms 5444 KB Output is correct
4 Correct 37 ms 5572 KB Output is correct
5 Correct 31 ms 5452 KB Output is correct
6 Correct 26 ms 5444 KB Output is correct
7 Correct 35 ms 5404 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 5324 KB Output is correct
2 Correct 29 ms 5288 KB Output is correct
3 Correct 29 ms 5376 KB Output is correct
4 Correct 24 ms 5316 KB Output is correct
5 Correct 32 ms 5268 KB Output is correct
6 Correct 23 ms 5380 KB Output is correct
7 Correct 23 ms 5324 KB Output is correct
8 Runtime error 365 ms 191456 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5452 KB Output is correct
2 Correct 29 ms 5464 KB Output is correct
3 Correct 34 ms 5444 KB Output is correct
4 Correct 37 ms 5572 KB Output is correct
5 Correct 31 ms 5452 KB Output is correct
6 Correct 26 ms 5444 KB Output is correct
7 Correct 35 ms 5404 KB Output is correct
8 Runtime error 457 ms 193464 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -