oj.uz

Submission #152101

# Submission time Handle Problem Language Result Execution time Memory
152101 2019-09-06T12:30:30 Z gs18103 None (KOI18_matrix) C++14
23 / 100
 4000 ms 12308 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 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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 988 KB Output is correct
2 Correct 68 ms 1268 KB Output is correct
3 Correct 69 ms 1140 KB Output is correct
4 Correct 67 ms 1140 KB Output is correct
5 Correct 68 ms 1188 KB Output is correct
6 Correct 64 ms 1160 KB Output is correct
7 Correct 66 ms 1140 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 884 KB Output is correct
2 Correct 68 ms 1268 KB Output is correct
3 Correct 69 ms 1368 KB Output is correct
4 Correct 69 ms 1268 KB Output is correct
5 Correct 75 ms 1396 KB Output is correct
6 Correct 65 ms 1200 KB Output is correct
7 Correct 69 ms 1268 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 988 KB Output is correct
2 Correct 68 ms 1268 KB Output is correct
3 Correct 69 ms 1140 KB Output is correct
4 Correct 67 ms 1140 KB Output is correct
5 Correct 68 ms 1188 KB Output is correct
6 Correct 64 ms 1160 KB Output is correct
7 Correct 66 ms 1140 KB Output is correct
8 Execution timed out 4098 ms 10136 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 884 KB Output is correct
2 Correct 68 ms 1268 KB Output is correct
3 Correct 69 ms 1368 KB Output is correct
4 Correct 69 ms 1268 KB Output is correct
5 Correct 75 ms 1396 KB Output is correct
6 Correct 65 ms 1200 KB Output is correct
7 Correct 69 ms 1268 KB Output is correct
8 Execution timed out 4014 ms 12308 KB Time limit exceeded
9 Halted 0 ms 0 KB -