oj.uz

Submission #64029

# Submission time Handle Problem Language Result Execution time Memory
64029 2018-08-03T08:28:03 Z kjp4155 None (KOI18_matrix) C++17
100 / 100
 663 ms 25112 KB 
#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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 10168 KB Output is correct
2 Correct 22 ms 10240 KB Output is correct
3 Correct 20 ms 10240 KB Output is correct
4 Correct 21 ms 10240 KB Output is correct
5 Correct 20 ms 10352 KB Output is correct
6 Correct 20 ms 10732 KB Output is correct
7 Correct 22 ms 10732 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 10732 KB Output is correct
2 Correct 30 ms 10732 KB Output is correct
3 Correct 31 ms 10732 KB Output is correct
4 Correct 28 ms 10732 KB Output is correct
5 Correct 32 ms 10732 KB Output is correct
6 Correct 31 ms 10732 KB Output is correct
7 Correct 31 ms 10732 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 10168 KB Output is correct
2 Correct 22 ms 10240 KB Output is correct
3 Correct 20 ms 10240 KB Output is correct
4 Correct 21 ms 10240 KB Output is correct
5 Correct 20 ms 10352 KB Output is correct
6 Correct 20 ms 10732 KB Output is correct
7 Correct 22 ms 10732 KB Output is correct
8 Correct 267 ms 16936 KB Output is correct
9 Correct 329 ms 16996 KB Output is correct
10 Correct 377 ms 17572 KB Output is correct
11 Correct 260 ms 17572 KB Output is correct
12 Correct 348 ms 17572 KB Output is correct
13 Correct 320 ms 20156 KB Output is correct
14 Correct 311 ms 20156 KB Output is correct
15 Correct 348 ms 20156 KB Output is correct
16 Correct 270 ms 24900 KB Output is correct
17 Correct 324 ms 24900 KB Output is correct
18 Correct 324 ms 24900 KB Output is correct
19 Correct 320 ms 24900 KB Output is correct
20 Correct 305 ms 24900 KB Output is correct

Subtask #4
62.0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 10732 KB Output is correct
2 Correct 30 ms 10732 KB Output is correct
3 Correct 31 ms 10732 KB Output is correct
4 Correct 28 ms 10732 KB Output is correct
5 Correct 32 ms 10732 KB Output is correct
6 Correct 31 ms 10732 KB Output is correct
7 Correct 31 ms 10732 KB Output is correct
8 Correct 451 ms 24900 KB Output is correct
9 Correct 438 ms 24900 KB Output is correct
10 Correct 381 ms 24900 KB Output is correct
11 Correct 393 ms 25112 KB Output is correct
12 Correct 389 ms 25112 KB Output is correct
13 Correct 391 ms 25112 KB Output is correct
14 Correct 458 ms 25112 KB Output is correct
15 Correct 378 ms 25112 KB Output is correct
16 Correct 383 ms 25112 KB Output is correct
17 Correct 461 ms 25112 KB Output is correct
18 Correct 601 ms 25112 KB Output is correct
19 Correct 364 ms 25112 KB Output is correct
20 Correct 398 ms 25112 KB Output is correct
21 Correct 369 ms 25112 KB Output is correct
22 Correct 492 ms 25112 KB Output is correct
23 Correct 550 ms 25112 KB Output is correct
24 Correct 369 ms 25112 KB Output is correct
25 Correct 432 ms 25112 KB Output is correct
26 Correct 663 ms 25112 KB Output is correct
27 Correct 376 ms 25112 KB Output is correct
28 Correct 432 ms 25112 KB Output is correct
29 Correct 410 ms 25112 KB Output is correct
30 Correct 419 ms 25112 KB Output is correct
31 Correct 663 ms 25112 KB Output is correct
32 Correct 486 ms 25112 KB Output is correct