제출 #109556

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
109556		aer0park	조화행렬 (KOI18_matrix)	C++14	29 / 100	499 ms	21720 KiB

matrix

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct el{
    el(ll _x,ll _y,ll _z):x(_x),y(_y),z(_z) { }
    ll x,y,z;
};

bool cmp(el a,el b)
{
   	return a.x<b.x;
}
ll m,n,ar[4][200005],pw[3][200014],anw;
vector<ll> arr[4];
vector<el> q;

ll sum(ll a,ll b)
{
	ll ret=-1;
	while(a)
	{
		ret=max(pw[b][a],ret);
		a-=(a&-a);
	}
	return ret;
}

void upd(ll a,ll b,ll x)
{
	while(a<=n)
	{
		pw[b][a]=max(x,pw[b][a]);
		a+=(a&-a);
	}
}

int main()
{
    //ios::sync_with_stdio(false);
    //cin.tie(NULL);
    cin>>m>>n;
    for(int j=0;j<m;j++)
        for(int i=1;i<=n;i++)
        {
            cin>>ar[j+1][i];
            arr[j].push_back(ar[j+1][i]);
        }
    if(m==2)
        for(int i=0;i<n;i++)
            arr[2].push_back(arr[1][i]);
    for(int j=0;j<3;j++)
        sort(arr[j].begin(),arr[j].end());
    for(int j=0;j<3;j++)
        for(int i=0;i<n;i++)
            ar[j+1][i+1]=lower_bound(arr[j].begin(),arr[j].end(),ar[j+1][i+1])-arr[j].begin()+1;
    for(int i=1;i<=n;i++)
        q.push_back(el(ar[1][i],ar[2][i],ar[3][i]));
    sort(q.begin(),q.end(),cmp);
	for(int i=0;i<n;i++)
	{
		ll a=min(sum(q[i].y,0),sum(q[i].z,1))+1;
		anw=max(anw,a);
		upd(q[i].y,0,a),upd(q[i].z,1,a);
	}
	cout<<anw;
    return 0;
}

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