Submission #64029

#	Time	Username	Problem	Language	Result	Execution time	Memory
64029		kjp4155	조화행렬 (KOI18_matrix)	C++17	100 / 100	663 ms	25112 KiB

matrix

#include <stdio.h>
#include <algorithm>
#include <utility>
#include <vector>
#include <set>
using namespace std;

typedef long long ll;

const int inf = 1e9;

int N,M;
// 주어진 행렬을 좌표압축 이후에 저장할 벡터
// { 1행, {2행, 3행}} 의 형식으로 저장된다
vector< pair<int, pair<int,int>> > v;
// 가중치가 k인 점들을 관리하기 위한 set
set<pair<int,int>> s[200500];

int p[4][200500];

int dp[200500];

// (x,y)보다 왼쪽 아래에 가중치 k인 점이 존재하는가?
bool chk_point(int x, int y, int k){
	auto it = s[k].lower_bound({x, -inf});
	if( it == s[k].begin() ) return false;
	it--;
	return (*it).second < y;
}

// 가중치 k를 가지는 점 (x,y)를 추가한다
// 이 과정에서 자신보다 왼쪽 아래 점, 오른쪽 위의 점을 모두 지우는 것으로 lower envelope를 잘 유지한다.
void add_point(int x, int y, int k){
	// 왼쪽 아래 점 모두 지우기
	while( true ){
		auto it = s[k].lower_bound({x, -inf});
		if( it == s[k].begin() ) break;
		it--;
		if( (*it).second < y ) s[k].erase(it);
		else break;
	}
	// 오른쪽 아래 점 모두 지우기
	while( true ){
		auto it = s[k].lower_bound({x+1, -inf});
		if( it == s[k].end() ) break;
		if( (*it).second >= y ) s[k].erase(it);
		else break;
	}
	
	s[k].insert({x,y});
}

int main(){
	scanf("%d%d",&M,&N);
	for(int i=1;i<=M;i++){
		for(int j=1;j<=N;j++) scanf("%d",&p[i][j]);
	}
	
	// 좌표압축
	for(int i=1;i<=M;i++){
		vector<int> tv; tv.push_back(-100);
		for(int j=1;j<=N;j++) tv.push_back(p[i][j]);
		sort(tv.begin(), tv.end());
		for(int j=1;j<=N;j++) p[i][j] = lower_bound(tv.begin(), tv.end(), p[i][j]) - tv.begin();
	}
	
	// M = 2 인 경우, 따로 처리하지 말고 두번째 행을 세번째로 복사해서 M = 3 인 경우로 만들자
	if( M == 2 ){
		for(int i=1;i<=N;i++) p[3][i] = p[2][i];
	}

	// 좌표압축 된 결과물을 v에 넣어준다
	for(int i=1;i<=N;i++){
		v.push_back({p[1][i], {p[2][i], p[3][i]}});
	}

	// 첫번째 행 기준으로 정렬해 준다
	sort(v.begin(), v.end());

	// 본격적으로 DP값을 계산한다
	for(int i=0;i<N;i++){
		int x = v[i].second.first, y = v[i].second.second;

		// 먼저, k에 대한 이분탐색으로 자신보다 왼쪽 아래에 있는 최대의 가중치 k를 구한다
		int low = 1, high = 200000, k = 0;
		while( low <= high ){
			int mid = (low+high)/2;
			if( chk_point(x,y,mid) ){
				k = mid; low = mid+1;
			}
			else high = mid-1;
		}

		// 현재 dp값을 업데이트
		dp[i] = k+1;

		// 새로운 점을 추가해 준다
		add_point(x,y,dp[i]);

	}

	int ans = -1;
	for(int i=0;i<N;i++) ans = max(ans, dp[i]);
	printf("%d\n",ans);

}

Compilation message (stderr)

matrix.cpp: In function 'int main()':
matrix.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&M,&N);
  ~~~~~^~~~~~~~~~~~~~
matrix.cpp:56:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int j=1;j<=N;j++) scanf("%d",&p[i][j]);
                         ~~~~~^~~~~~~~~~~~~~~

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