Submission #109751

#	Time	Username	Problem	Language	Result	Execution time	Memory
109751		aer0park	조화행렬 (KOI18_matrix)	C++14	29 / 100	323 ms	22992 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 val(ll a,ll b)
{
	ll ret=0;
	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]);
        	ar[3][i+1]=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(val(q[i].y-1,0),val(q[i].z-1,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