Submission #67342

#	Time	Username	Problem	Language	Result	Execution time	Memory
67342		h0ngjun7	조화행렬 (KOI18_matrix)	C++17	100 / 100	3151 ms	101464 KiB

matrix

#include <bits/stdc++.h>
using namespace std;
#define N (200000)
struct Node{
	int a[3];
	Node(){}
	Node(int x, int y, int z){a[0]=x;a[1]=y;a[2]=z;}
};
int ctl, tree[8*N], dp[N], n;;
int cmp(Node x, Node y){return x.a[ctl] < y.a[ctl];}
Node f[N], tmp1[N], tmp2[N];
vector<int> v;
void push(int x, int pos, int L, int R, int val){
	if(pos < L || pos > R)return;
	if(pos == L && pos == R){
		tree[x] = val;
		return;
	}
	int mid = (L+R)/2;
	push(2*x, pos, L, mid, val);
	push(2*x+1, pos, mid+1, R, val);
	tree[x] = max(tree[x*2], tree[2*x+1]);
	return;
}
int get(int x, int l, int r, int L, int R){
	if(l > R || r < L)return 0;
	if(l <= L && R <= r)return tree[x];
	int mid = (L + R) / 2;
	return max(get(2*x, l, r, L, mid), get(2*x+1, l, r, mid+1, R));
}
void solve(int l, int r){
	if(l == r){dp[l]++;return;}
	int mid = (l+r)/2;
	solve(l, mid);
	for(int i=l; i<=mid; i++)tmp1[i] = f[i], tmp1[i].a[0]=i;
	for(int i=mid+1; i<=r; i++)tmp2[i] = f[i], tmp2[i].a[0]=i;
	sort(tmp1+l, tmp1+mid+1, cmp);
	sort(tmp2+mid+1, tmp2+r+1, cmp);
	int ll=l, rr=mid+1;
	while(ll < mid+1 || rr <= r){
		if(ll < mid+1 && tmp1[ll].a[1] < tmp2[rr].a[1] || rr > r){
			push(1, tmp1[ll].a[2], 0, n-1, dp[tmp1[ll].a[0]]);
			ll++;
		}
		else{
			dp[tmp2[rr].a[0]] = max(get(1, 0, tmp2[rr].a[2]-1, 0, n-1), dp[tmp2[rr].a[0]]);
			rr++;
		}
	}
	for(int i=l; i<=mid; i++)push(1, tmp1[i].a[2], 0, n-1, 0);
	solve(mid+1, r);
}
int main(){
	int m,ans=0;
	scanf("%d %d", &m, &n);
	for(int i=0; i<m; i++)for(int j=0; j<n; j++)scanf("%d", &f[j].a[i]);
	sort(f, f+n, cmp);
	if(m == 2){
		v.push_back(0);
		for(int i=0; i<n; i++){
			auto it = lower_bound(v.begin(), v.end(), f[i].a[1]);
			if(it == v.end())v.push_back(f[i].a[1]);
			else *it = f[i].a[1];
		}
		printf("%d\n", v.size()-1);
	}
	else{
		ctl=1;
		for(int idx=1; idx<3; idx++){
			map<int, int> mp;
			for(int i=0; i<n; i++)mp[f[i].a[idx]]=0;
			int a = 0;
			for(auto it=mp.begin(); it != mp.end(); it++)it->second=a++;
			for(int i=0; i<n; i++)f[i].a[idx] = mp[f[i].a[idx]];
		}
		solve(0, n-1);
		for(int i=0; i<n; i++)ans=max(ans, dp[i]);
		printf("%d\n", ans);
	}
	return 0;
}

Compilation message (stderr)

matrix.cpp: In function 'void solve(int, int)':
matrix.cpp:41:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if(ll < mid+1 && tmp1[ll].a[1] < tmp2[rr].a[1] || rr > r){
      ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
matrix.cpp: In function 'int main()':
matrix.cpp:65:28: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
   printf("%d\n", v.size()-1);
                  ~~~~~~~~~~^
matrix.cpp:55: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:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<m; i++)for(int j=0; j<n; j++)scanf("%d", &f[j].a[i]);
                                              ~~~~~^~~~~~~~~~~~~~~~~~

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