oj.uz

Submission #152103

# Submission time Handle Problem Language Result Execution time Memory
152103 2019-09-06T12:45:44 Z gs18103 None (KOI18_matrix) C++14
100 / 100
 1378 ms 18756 KB 
#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 row {
	int x, y, z;
};

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

struct Fwt {
	int tree[202020];

	void init(int k) {
		for(int i = 0; i <= k+10; 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 m = s + e >> 1;
	dnc(s, m);

	vector <row> l, r;
	vector <int> X, Y;
	for(int i = s; i <= m; i++) {
		l.eb(arr[i]), X.eb(arr[i].x), Y.eb(arr[i].y);
	}
	for(int i = m+1; i <= e; i++) {
		r.eb(arr[i]), X.eb(arr[i].x), Y.eb(arr[i].y);
	}
	sort(all(l), [](row a, row b) {
		return a.x < b.x;
	});
	sort(all(r), [](row a, row b) {
		return a.x < b.x;
	});
	sort(all(X)), sort(all(Y));
	for(int i = 0; i < l.size(); i++) {
		l[i].x = lower_bound(all(X), l[i].x)-X.begin()+1;
		l[i].y = lower_bound(all(Y), l[i].y)-Y.begin()+1;
	}
	for(int i = 0; i < r.size(); i++) {
		r[i].x = lower_bound(all(X), r[i].x)-X.begin()+1;
		r[i].y = lower_bound(all(Y), r[i].y)-Y.begin()+1;
	}
	fwt.init(X.size());
	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(m+1, e);
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> M >> n;
	for(int i = 1; i <= n; i++) {
		cin >> arr[i].x;
	}
	for(int i = 1; i <= n; i++) {
		cin >> arr[i].y;
	}
	for(int i = 1; i <= n; i++) {
		if(M == 3) cin >> arr[i].z;
		else arr[i].z = arr[i].y;
	}

	sort(arr+1, arr+n+1, [](row a, row 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

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

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 1064 KB Output is correct
2 Correct 41 ms 1072 KB Output is correct
3 Correct 42 ms 1072 KB Output is correct
4 Correct 40 ms 1068 KB Output is correct
5 Correct 42 ms 1072 KB Output is correct
6 Correct 31 ms 1044 KB Output is correct
7 Correct 37 ms 1080 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 1072 KB Output is correct
2 Correct 40 ms 1072 KB Output is correct
3 Correct 47 ms 1044 KB Output is correct
4 Correct 50 ms 1072 KB Output is correct
5 Correct 45 ms 1084 KB Output is correct
6 Correct 33 ms 1072 KB Output is correct
7 Correct 48 ms 1060 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 1064 KB Output is correct
2 Correct 41 ms 1072 KB Output is correct
3 Correct 42 ms 1072 KB Output is correct
4 Correct 40 ms 1068 KB Output is correct
5 Correct 42 ms 1072 KB Output is correct
6 Correct 31 ms 1044 KB Output is correct
7 Correct 37 ms 1080 KB Output is correct
8 Correct 1175 ms 12728 KB Output is correct
9 Correct 1158 ms 16676 KB Output is correct
10 Correct 990 ms 16784 KB Output is correct
11 Correct 704 ms 16508 KB Output is correct
12 Correct 1126 ms 16652 KB Output is correct
13 Correct 789 ms 16616 KB Output is correct
14 Correct 1095 ms 16660 KB Output is correct
15 Correct 703 ms 16684 KB Output is correct
16 Correct 779 ms 16892 KB Output is correct
17 Correct 769 ms 16720 KB Output is correct
18 Correct 928 ms 16636 KB Output is correct
19 Correct 1048 ms 16664 KB Output is correct
20 Correct 1171 ms 16740 KB Output is correct

Subtask #4
62.0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 1072 KB Output is correct
2 Correct 40 ms 1072 KB Output is correct
3 Correct 47 ms 1044 KB Output is correct
4 Correct 50 ms 1072 KB Output is correct
5 Correct 45 ms 1084 KB Output is correct
6 Correct 33 ms 1072 KB Output is correct
7 Correct 48 ms 1060 KB Output is correct
8 Correct 1173 ms 12852 KB Output is correct
9 Correct 1168 ms 18464 KB Output is correct
10 Correct 1008 ms 18544 KB Output is correct
11 Correct 799 ms 18508 KB Output is correct
12 Correct 1259 ms 18628 KB Output is correct
13 Correct 1105 ms 18500 KB Output is correct
14 Correct 1284 ms 18652 KB Output is correct
15 Correct 798 ms 18584 KB Output is correct
16 Correct 833 ms 18708 KB Output is correct
17 Correct 1186 ms 18520 KB Output is correct
18 Correct 1378 ms 18492 KB Output is correct
19 Correct 1004 ms 18680 KB Output is correct
20 Correct 1277 ms 18756 KB Output is correct
21 Correct 811 ms 18640 KB Output is correct
22 Correct 1352 ms 18700 KB Output is correct
23 Correct 1171 ms 18576 KB Output is correct
24 Correct 999 ms 18696 KB Output is correct
25 Correct 1328 ms 18532 KB Output is correct
26 Correct 1190 ms 18684 KB Output is correct
27 Correct 1259 ms 18544 KB Output is correct
28 Correct 833 ms 18636 KB Output is correct
29 Correct 1178 ms 18624 KB Output is correct
30 Correct 1170 ms 18664 KB Output is correct
31 Correct 1189 ms 18636 KB Output is correct
32 Correct 1166 ms 18464 KB Output is correct