Submission #166379

#	Time	Username	Problem	Language	Result	Execution time	Memory
166379		knon0501	조화행렬 (KOI18_matrix)	C++14	100 / 100	2303 ms	90820 KiB

matrix

#include <bits/stdc++.h>
using namespace std;
int m,n;
const int MX=2e5+5;
struct A{
    int x,y,z;
    bool operator <(const A&r){
        return x<r.x;
    }
}a[MX];
struct Node{
    int l,r,v;
}seg[MX*20];
int tree[MX];
int dp[MX];
map<int,int> mp1;
map<int,int> mp2;
int nn;

int f(int lef,int rig,int k,int lev){
    if(lef>k || lev==0)return 2e9;
    if(rig<=k)return seg[lev].v;
    int mid=(lef+rig)/2;
    return min(f(lef,mid,k,seg[lev].l),f(mid+1,rig,k,seg[lev].r));
}
void upd(int lef,int rig,int x,int y,int lev){
    seg[lev].v=min(seg[lev].v,y);
    if(lef==rig)return;
    int mid=(lef+rig)/2;
    if(x<=mid){
        if(!seg[lev].l)seg[seg[lev].l=++nn].v=2e9;
        upd(lef,mid,x,y,seg[lev].l);
    }
    else{
        if(!seg[lev].r)seg[seg[lev].r=++nn].v=2e9;
        upd(mid+1,rig,x,y,seg[lev].r);
    }
}
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>m>>n;
    int i,j;
    for(i=1 ; i<=n ; i++)cin>>a[i].x;
    for(i=1 ; i<=n ; i++)cin>>a[i].y;
    for(i=1 ; i<=n ; i++)cin>>a[i].z;
    for(i=1 ; i<=n ; i++)seg[tree[i]=i].v=2e9;
    nn=n;
    set<int> S1;
    set<int> S2;
    sort(a+1,a+n+1);
    for(i=1 ; i<=n ; i++){
        S1.insert(a[i].y);
        S2.insert(a[i].z);
    }
    int cnt=0;
    for(auto k: S1)mp1[k]=++cnt;cnt=0;
    for(auto k: S2)mp2[k]=++cnt;
    int ans=0;
    for(i=1 ; i<=n ; i++){
        int lef=1;
        int rig=n;
        int k=0;
        while(rig>=lef){
            int mid=(lef+rig)/2;
            if(f(1,n,mp1[a[i].y],tree[mid])<=mp2[a[i].z]){
                k=mid;
                lef=mid+1;
            }
            else
                rig=mid-1;
        }
        ans=max(ans,k+1);
        upd(1,n,mp1[a[i].y],mp2[a[i].z],tree[k+1]);
    }
    cout<<ans;
    return 0;
}

Compilation message (stderr)

matrix.cpp: In function 'int main()':
matrix.cpp:57:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(auto k: S1)mp1[k]=++cnt;cnt=0;
     ^~~
matrix.cpp:57:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(auto k: S1)mp1[k]=++cnt;cnt=0;
                                 ^~~
matrix.cpp:43:11: warning: unused variable 'j' [-Wunused-variable]
     int i,j;
           ^

• Subtask 1: 14 / 14
• Subtask 2: 9 / 9
• Subtask 3: 15 / 15
• Subtask 4: 62 / 62