| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1098688 |
2024-10-09T17:49:14 Z |
ortsac |
Lottery (CEOI18_lot) |
C++17 |
|
6 ms |
3928 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
int n, x;
struct SegTree {
int seg[4*MAXN];
void build() {
memset(seg, 0, sizeof seg);
}
void update(int node, int l, int r, int po, int val) {
if (l == r) {
seg[node] = max(seg[node], val);
return;
}
int m = (l+r)/2;
if (po <= m) update(2*node, l, m, po, val);
else update(2*node + 1, m + 1, r, po, val);
seg[node] = max(seg[2*node], seg[2*node + 1]);
}
int query(int node, int l, int r, int tl, int tr) {
if (r < l) return 0;
if ((r < tl) || (tr < l)) return 0;
if ((tl <= l) && (r <= tr)) return seg[node];
int m = (l+r)/2;
return max(query(2*node, l, m, tl, tr), query(2*node + 1, m + 1, r, tl, tr));
}
};
int32_t main() {
cin >> n >> x;
vector<int> v(n);
for (int i = 0; i < n; i++) cin >> v[i];
vector<int> ord = v;
sort(ord.begin(), ord.end());
ord.erase(unique(ord.begin(), ord.end()), ord.end());
map<int, int> re;
for (int i = 0; i < ((int)ord.size()); i++) re[ord[i]] = i;
// calc prefix
SegTree seg;
seg.build();
vector<int> pf(n);
for (int i = 0; i < n; i++) {
// calcular pf[i]
// posso pegar até v[i]+x
auto it = lower_bound(ord.begin(), ord.end(), v[i] + x);
int mxPo = (it - ord.begin() - 1);
//cout << "this is mxpo: " << mxPo << "\n";
pf[i] = seg.query(1, 0, n - 1, 0, mxPo);
// atualizar aqui
int po = re[v[i]];
int mx = seg.query(1, 0, n - 1, 0, po - 1);
//cout << mx << "\n";
seg.update(1, 0, n - 1, po, mx + 1);
}
seg.build();
int ans = 0;
for (int i = n - 1; i >= 0; i--) {
// atualizar aqui
int po = re[v[i]];
int mx = seg.query(1, 0, n - 1, po + 1, n - 1);
seg.update(1, 0, n - 1, po, mx + 1);
ans = max(ans, mx + 1 + pf[i]);
//cout << i << " " << mx << " " << pf[i] << "\n";
}
cout << ans << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
3928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
3928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
