# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
393325 |
2021-04-23T07:57:04 Z |
palilo |
None (KOI18_matrix) |
C++17 |
|
227 ms |
27264 KB |
#include <bits/stdc++.h>
using namespace std;
void solve2() {
int n;
cin >> n;
vector<pair<int, int>> a(n);
for (auto& [x, _] : a) cin >> x;
for (auto& [_, y] : a) cin >> y;
sort(a.begin(), a.end(), [&](auto& a, auto& b) {
return a.first < b.first;
});
vector<int> dp;
for (const auto& [_, y] : a)
if (auto it = lower_bound(dp.begin(), dp.end(), y); it == dp.end())
dp.emplace_back(y);
else
*it = y;
cout << dp.size();
}
void solve3() {
int n;
cin >> n;
vector<tuple<int, int, int>> a(n);
for (auto& [x, y, z] : a) cin >> x;
for (auto& [x, y, z] : a) cin >> y;
for (auto& [x, y, z] : a) cin >> z;
sort(a.begin(), a.end(), [](auto& a, auto& b) {
return get<0>(a) < get<0>(b);
});
vector<set<pair<int, int>>> dp;
auto ok = [&](int set_id, pair<int, int> point) {
auto it = dp[set_id].lower_bound(point);
return it == dp[set_id].begin() || prev(it)->second > point.second;
};
for (const auto& [_, y, z] : a) {
int lo = 0, hi = dp.size();
while (lo != hi) {
int mid = (lo + hi) >> 1;
ok(mid, make_pair(y, z)) ? hi = mid : lo = mid + 1;
}
if (lo == dp.size())
dp.emplace_back(set<pair<int, int>> {{y, z}});
else
for (auto it = next(dp[lo].emplace(y, z).first); it != dp[lo].end(); it = dp[lo].erase(it))
if (it->second < z)
break;
}
cout << dp.size();
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
#ifdef home
freopen("in", "r", stdin);
freopen("out", "w", stdout);
#endif
int m;
cin >> m;
m == 2 ? solve2() : solve3();
}
Compilation message
matrix.cpp: In function 'void solve3()':
matrix.cpp:50:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::set<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | if (lo == dp.size())
| ~~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
592 KB |
Output is correct |
2 |
Correct |
4 ms |
592 KB |
Output is correct |
3 |
Correct |
4 ms |
592 KB |
Output is correct |
4 |
Correct |
4 ms |
592 KB |
Output is correct |
5 |
Correct |
4 ms |
592 KB |
Output is correct |
6 |
Correct |
4 ms |
612 KB |
Output is correct |
7 |
Correct |
5 ms |
592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
1060 KB |
Output is correct |
2 |
Correct |
7 ms |
1108 KB |
Output is correct |
3 |
Correct |
8 ms |
800 KB |
Output is correct |
4 |
Correct |
9 ms |
756 KB |
Output is correct |
5 |
Correct |
8 ms |
892 KB |
Output is correct |
6 |
Correct |
8 ms |
1808 KB |
Output is correct |
7 |
Correct |
9 ms |
720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
592 KB |
Output is correct |
2 |
Correct |
4 ms |
592 KB |
Output is correct |
3 |
Correct |
4 ms |
592 KB |
Output is correct |
4 |
Correct |
4 ms |
592 KB |
Output is correct |
5 |
Correct |
4 ms |
592 KB |
Output is correct |
6 |
Correct |
4 ms |
612 KB |
Output is correct |
7 |
Correct |
5 ms |
592 KB |
Output is correct |
8 |
Correct |
79 ms |
5712 KB |
Output is correct |
9 |
Correct |
75 ms |
5708 KB |
Output is correct |
10 |
Correct |
74 ms |
6104 KB |
Output is correct |
11 |
Correct |
66 ms |
5708 KB |
Output is correct |
12 |
Correct |
74 ms |
5788 KB |
Output is correct |
13 |
Correct |
74 ms |
6344 KB |
Output is correct |
14 |
Correct |
76 ms |
5832 KB |
Output is correct |
15 |
Correct |
74 ms |
5712 KB |
Output is correct |
16 |
Correct |
69 ms |
6828 KB |
Output is correct |
17 |
Correct |
71 ms |
6348 KB |
Output is correct |
18 |
Correct |
74 ms |
6352 KB |
Output is correct |
19 |
Correct |
73 ms |
5968 KB |
Output is correct |
20 |
Correct |
75 ms |
5708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
1060 KB |
Output is correct |
2 |
Correct |
7 ms |
1108 KB |
Output is correct |
3 |
Correct |
8 ms |
800 KB |
Output is correct |
4 |
Correct |
9 ms |
756 KB |
Output is correct |
5 |
Correct |
8 ms |
892 KB |
Output is correct |
6 |
Correct |
8 ms |
1808 KB |
Output is correct |
7 |
Correct |
9 ms |
720 KB |
Output is correct |
8 |
Correct |
151 ms |
13184 KB |
Output is correct |
9 |
Correct |
136 ms |
11484 KB |
Output is correct |
10 |
Correct |
173 ms |
18100 KB |
Output is correct |
11 |
Correct |
131 ms |
27264 KB |
Output is correct |
12 |
Correct |
107 ms |
8392 KB |
Output is correct |
13 |
Correct |
151 ms |
15252 KB |
Output is correct |
14 |
Correct |
178 ms |
10824 KB |
Output is correct |
15 |
Correct |
138 ms |
17812 KB |
Output is correct |
16 |
Correct |
135 ms |
17776 KB |
Output is correct |
17 |
Correct |
138 ms |
11484 KB |
Output is correct |
18 |
Correct |
217 ms |
8780 KB |
Output is correct |
19 |
Correct |
106 ms |
8412 KB |
Output is correct |
20 |
Correct |
161 ms |
11824 KB |
Output is correct |
21 |
Correct |
131 ms |
17804 KB |
Output is correct |
22 |
Correct |
211 ms |
9288 KB |
Output is correct |
23 |
Correct |
136 ms |
11484 KB |
Output is correct |
24 |
Correct |
108 ms |
8420 KB |
Output is correct |
25 |
Correct |
198 ms |
9952 KB |
Output is correct |
26 |
Correct |
227 ms |
17788 KB |
Output is correct |
27 |
Correct |
107 ms |
8392 KB |
Output is correct |
28 |
Correct |
131 ms |
17808 KB |
Output is correct |
29 |
Correct |
137 ms |
11480 KB |
Output is correct |
30 |
Correct |
138 ms |
11488 KB |
Output is correct |
31 |
Correct |
213 ms |
17752 KB |
Output is correct |
32 |
Correct |
142 ms |
11592 KB |
Output is correct |