Submission #152101

#	Time	Username	Problem	Language	Result	Execution time	Memory
152101		gs18103	조화행렬 (KOI18_matrix)	C++14	23 / 100	4098 ms	12308 KiB

matrix

#include <bits/stdc++.h>
#define eb emplace_back
#define fi first
#define se second
#define all(v) v.begin(), v.end()

using namespace std;
typedef pair <int, int> pii;

struct tp3 {
	int x, y, z;
};

tp3 arr[202020];
int dp[202020], M, n;

struct Fwt {
	int tree[202020];

	void init() {
		for(int i = 1; i <= n; i++) tree[i] = 0;
	}

	void update(int i, int val) {
		while(i <= n) {
			tree[i] = max(tree[i], val);
			i += (i & -i);
		}
	}
	int cal(int i) {
		int ret = 0;
		while(i > 0) {
			ret = max(ret, tree[i]);
			i -= (i & -i);
		}
		return ret;
	}
} fwt;

void dnc(int s, int e) {
	if(s == e) {
		dp[s] = max(dp[s], 1);
		return;
	}
	int mi = s + e >> 1;
	dnc(s, mi);
	vector <tp3> l, r;
	fwt.init();
	for(int i = s; i <= mi; i++) {
		l.eb(arr[i]);
	}
	for(int i = mi + 1; i <= e; i++) {
		r.eb(arr[i]);
	}
	sort(all(l), [](tp3 a, tp3 b) {
		return a.x < b.x;
	});
	sort(all(r), [](tp3 a, tp3 b) {
		return a.x < b.x;
	});
	int idx = 0;
	for(int i = 0; i < r.size(); i++) {
		while(idx < l.size() && l[idx].x < r[i].x) {
			fwt.update(l[idx].y, dp[l[idx].z]);
			idx++;
		}
		dp[r[i].z] = max(dp[r[i].z], fwt.cal(r[i].y-1) + 1);
	}
	dnc(mi+1, e);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> M >> n;
	vector <int> X, Y, Z;
	for(int i = 1; i <= n; i++) {
		cin >> arr[i].x;
		X.eb(arr[i].x);
	}
	for(int i = 1; i <= n; i++) {
		cin >> arr[i].y;
		Y.eb(arr[i].y);
	}
	if(M == 3) {
		for(int i = 1; i <= n; i++) {
			cin >> arr[i].z;
		} 
	}
	else {
		for(int i = 1; i <= n; i++) {
			arr[i].z = arr[i].y;
		}
	}
	sort(all(X)), sort(all(Y));
	for(int i = 1; i <= n; i++) {
		arr[i].x = lower_bound(all(X), arr[i].x)-X.begin()+1;
		arr[i].y = lower_bound(all(Y), arr[i].y)-Y.begin()+1;
	};
	sort(arr+1, arr+n+1, [](tp3 a, tp3 b) {
		return a.z < b.z;
	});
	for(int i = 1; i <= n; i++) {
		arr[i].z = i;
	}
	dnc(1, n);
	int ans = 0;
	for(int i = 1; i <= n; i++) {
		ans = max(ans, dp[i]);
	}
	cout << ans;
}

Compilation message (stderr)

matrix.cpp: In function 'void dnc(int, int)':
matrix.cpp:45:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mi = s + e >> 1;
           ~~^~~
matrix.cpp:62:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < r.size(); i++) {
                 ~~^~~~~~~~~~
matrix.cpp:63:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(idx < l.size() && l[idx].x < r[i].x) {
         ~~~~^~~~~~~~~~

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