# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
152101 |
2019-09-06T12:30:30 Z |
gs18103 |
None (KOI18_matrix) |
C++14 |
|
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) {
~~~~^~~~~~~~~~
# |
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 |
# |
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 |
# |
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 |
- |
# |
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 |
- |