# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1031689 |
2024-07-23T04:09:19 Z |
juicy |
Exhibition (JOI19_ho_t2) |
C++17 |
|
1 ms |
348 KB |
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
const int N = 1e5 + 5;
int n, m, sz;
int c[N];
array<int, 2> a[N], s[N];
void upd(int i, array<int, 2> x) {
for (; i <= sz; i += i & -i) {
s[i] = max(s[i], x);
}
}
array<int, 2> qry(int i) {
array<int, 2> res{};
for (; i; i -= i & -i) {
res = max(res, s[i]);
}
return res;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
vector<int> comp;
for (int i = 1; i <= n; ++i) {
cin >> a[i][0] >> a[i][1];
comp.push_back(a[i][1]);
}
for (int i = 1; i <= m; ++i) {
cin >> c[i];
}
sort(a + 1, a + n + 1);
sort(c + 1, c + m + 1);
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
sz = comp.size();
for (int i = 1; i <= n; ++i) {
a[i][1] = lower_bound(comp.begin(), comp.end(), a[i][1]) - comp.begin() + 1;
}
int ans = 0;
for (int i = 1, p = 0; i <= n; ++i) {
while (p <= m && c[p] < a[i][0]) {
++p;
}
auto res = qry(a[i][1]);
int nxt = max(1 - res[1], p);
if (nxt <= m) {
ans = max(ans, res[0] + 1);
upd(a[i][1], {res[0] + 1, -nxt});
}
}
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |