oj.uz

Submission #64022

# Submission time Handle Problem Language Result Execution time Memory
64022 2018-08-03T08:25:26 Z kjp4155 None (KOI18_matrix) C++17
100 / 100
 832 ms 149080 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:51: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:53: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 29 ms 10168 KB Output is correct
2 Correct 25 ms 10340 KB Output is correct
3 Correct 30 ms 10428 KB Output is correct
4 Correct 26 ms 10428 KB Output is correct
5 Correct 25 ms 10428 KB Output is correct
6 Correct 27 ms 10748 KB Output is correct
7 Correct 26 ms 10748 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 10748 KB Output is correct
2 Correct 37 ms 10920 KB Output is correct
3 Correct 32 ms 10960 KB Output is correct
4 Correct 41 ms 11304 KB Output is correct
5 Correct 36 ms 11784 KB Output is correct
6 Correct 31 ms 12332 KB Output is correct
7 Correct 35 ms 12332 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 10168 KB Output is correct
2 Correct 25 ms 10340 KB Output is correct
3 Correct 30 ms 10428 KB Output is correct
4 Correct 26 ms 10428 KB Output is correct
5 Correct 25 ms 10428 KB Output is correct
6 Correct 27 ms 10748 KB Output is correct
7 Correct 26 ms 10748 KB Output is correct
8 Correct 316 ms 18776 KB Output is correct
9 Correct 349 ms 18796 KB Output is correct
10 Correct 332 ms 19308 KB Output is correct
11 Correct 354 ms 19308 KB Output is correct
12 Correct 312 ms 19308 KB Output is correct
13 Correct 350 ms 21872 KB Output is correct
14 Correct 338 ms 21872 KB Output is correct
15 Correct 288 ms 21872 KB Output is correct
16 Correct 321 ms 26612 KB Output is correct
17 Correct 327 ms 26612 KB Output is correct
18 Correct 325 ms 26612 KB Output is correct
19 Correct 371 ms 26612 KB Output is correct
20 Correct 326 ms 26612 KB Output is correct

Subtask #4
62.0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 10748 KB Output is correct
2 Correct 37 ms 10920 KB Output is correct
3 Correct 32 ms 10960 KB Output is correct
4 Correct 41 ms 11304 KB Output is correct
5 Correct 36 ms 11784 KB Output is correct
6 Correct 31 ms 12332 KB Output is correct
7 Correct 35 ms 12332 KB Output is correct
8 Correct 475 ms 27252 KB Output is correct
9 Correct 548 ms 31976 KB Output is correct
10 Correct 477 ms 36060 KB Output is correct
11 Correct 443 ms 38612 KB Output is correct
12 Correct 407 ms 38612 KB Output is correct
13 Correct 473 ms 40720 KB Output is correct
14 Correct 532 ms 43088 KB Output is correct
15 Correct 489 ms 52836 KB Output is correct
16 Correct 475 ms 58688 KB Output is correct
17 Correct 607 ms 61372 KB Output is correct
18 Correct 691 ms 65636 KB Output is correct
19 Correct 461 ms 71336 KB Output is correct
20 Correct 495 ms 78768 KB Output is correct
21 Correct 484 ms 87888 KB Output is correct
22 Correct 604 ms 88872 KB Output is correct
23 Correct 521 ms 96280 KB Output is correct
24 Correct 439 ms 100528 KB Output is correct
25 Correct 606 ms 106368 KB Output is correct
26 Correct 781 ms 119920 KB Output is correct
27 Correct 484 ms 119920 KB Output is correct
28 Correct 488 ms 128504 KB Output is correct
29 Correct 545 ms 131116 KB Output is correct
30 Correct 637 ms 136956 KB Output is correct
31 Correct 832 ms 149080 KB Output is correct
32 Correct 553 ms 149080 KB Output is correct