Submission #65652

#	Time	Username	Problem	Language	Result	Execution time	Memory
65652		sebinkim	조화행렬 (KOI18_matrix)	C++14	100 / 100	665 ms	31316 KiB

matrix

#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;

vector <int> V;
set <pii> S[202020];
int A[202020], B[202020], C[202020];
int K[202020], L[202020];
int n, m, ans;

int get_lis(int* T)
{
	int i, k;
	
	for(i=1; i<=n; i++){
		k = lower_bound(L, L+ans+1, T[i]) - L;
		if(k > ans) ans = k;
		L[k] = T[i];
	}
}

bool check(int k, pii p)
{
	auto it = S[k].lower_bound(p);
	if(it == S[k].begin()) return false;
	else{
		it --;
		return it->second < p.second;
	}
}

void push(int k, pii p)
{
	for(; ; ){
		auto it = S[k].lower_bound(p);
		if(it == S[k].end()){
			S[k].insert(p);
			return;
		}
		else{
			if(it->second > p.second) S[k].erase(it);
			else{
				S[k].insert(p);
				return;
			}
		}
	}
}

int main()
{
	int i, b, c, s, e, mid;
	
	scanf("%d%d", &m, &n);
	
	for(i=1; i<=n; i++){
		scanf("%d", A+i);
		V.push_back(A[i]);
	}
	
	sort(V.begin(), V.end());
	V.erase(unique(V.begin(), V.end()), V.end());
	
	for(i=1; i<=n; i++){
		K[i] = lower_bound(V.begin(), V.end(), A[i]) - V.begin() + 1;
	}
	
	V.clear();
	
	for(i=1; i<=n; i++){
		scanf("%d", B+K[i]);
		V.push_back(B[K[i]]);
	}
	
	sort(V.begin(), V.end());
	V.erase(unique(V.begin(), V.end()), V.end());
	
	for(i=1; i<=n; i++){
		B[i] = lower_bound(V.begin(), V.end(), B[i]) - V.begin() + 1;
	}
	
	if(m == 2){
		get_lis(B);
		printf("%d\n", ans);
		return 0;
	}
	
	V.clear();
	
	for(i=1; i<=n; i++){
		scanf("%d", C+K[i]);
		V.push_back(C[K[i]]);
	}
	
	sort(V.begin(), V.end());
	V.erase(unique(V.begin(), V.end()), V.end());
	
	for(i=1; i<=n; i++){
		C[i] = lower_bound(V.begin(), V.end(), C[i]) - V.begin() + 1;
	}
	
	S[0].insert(pii(0, 0));
	
	for(i=1; i<=n; i++){
		b = B[i], c = C[i];
		for(s=0,e=ans;s<=e;){
			mid = s+e >> 1;
			if(check(mid, pii(b, c))) s = mid + 1;
			else e = mid - 1;
		}
		if(s > ans) ans = s;
		push(s, pii(b, c));
	}
	
	printf("%d\n", ans);
	
	return 0;
}

Compilation message (stderr)

matrix.cpp: In function 'int get_lis(int*)':
matrix.cpp:22:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
matrix.cpp: In function 'int main()':
matrix.cpp:109:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid = s+e >> 1;
          ~^~
matrix.cpp:56: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:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", A+i);
   ~~~~~^~~~~~~~~~~
matrix.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", B+K[i]);
   ~~~~~^~~~~~~~~~~~~~
matrix.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", C+K[i]);
   ~~~~~^~~~~~~~~~~~~~

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