Submission #423347

#	Time	Username	Problem	Language	Result	Execution time	Memory
423347		ansol4328	조화행렬 (KOI18_matrix)	C++14	100 / 100	2140 ms	100616 KiB

matrix

#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[524300];
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 (stderr)

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 / 14
• Subtask 2: 9 / 9
• Subtask 3: 15 / 15
• Subtask 4: 62 / 62