oj.uz

Submission #63997

# Submission time Handle Problem Language Result Execution time Memory
63997 2018-08-03T08:10:47 Z kjp4155 None (KOI18_matrix) C++17
29 / 100
 302 ms 69104 KB 
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <vector>
#include <set>
using namespace std;

typedef long long ll;

const ll inf = 1e18;

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 27 ms 10360 KB Output is correct
2 Correct 22 ms 10636 KB Output is correct
3 Correct 21 ms 10824 KB Output is correct
4 Correct 21 ms 11092 KB Output is correct
5 Correct 21 ms 11280 KB Output is correct
6 Correct 24 ms 11856 KB Output is correct
7 Correct 21 ms 11876 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 12240 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 10360 KB Output is correct
2 Correct 22 ms 10636 KB Output is correct
3 Correct 21 ms 10824 KB Output is correct
4 Correct 21 ms 11092 KB Output is correct
5 Correct 21 ms 11280 KB Output is correct
6 Correct 24 ms 11856 KB Output is correct
7 Correct 21 ms 11876 KB Output is correct
8 Correct 273 ms 22580 KB Output is correct
9 Correct 271 ms 26536 KB Output is correct
10 Correct 271 ms 31344 KB Output is correct
11 Correct 258 ms 34216 KB Output is correct
12 Correct 302 ms 38132 KB Output is correct
13 Correct 286 ms 45132 KB Output is correct
14 Correct 292 ms 45844 KB Output is correct
15 Correct 269 ms 49880 KB Output is correct
16 Correct 277 ms 61604 KB Output is correct
17 Correct 288 ms 61604 KB Output is correct
18 Correct 296 ms 65040 KB Output is correct
19 Correct 276 ms 65300 KB Output is correct
20 Correct 275 ms 69104 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 12240 KB Output isn't correct
2 Halted 0 ms 0 KB -