# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
427571 |
2021-06-14T17:19:35 Z |
Pety |
Global Warming (CEOI18_glo) |
C++14 |
|
646 ms |
262148 KB |
#include <bits/stdc++.h>
using namespace std;
int n, x, pref[200002], suf[200002], v[200002], norm[200002];
vector<int>aux;
int aint[4 * 3 * 200000 + 2];
unordered_map<int, int>mp;
void update (int nod, int st, int dr, int poz, int val) {
if (st == dr) {
aint[poz] = val;
return;
}
int mij = (st + dr) / 2;
if (poz <= mij)
update(2 * nod, st, mij, poz, val);
else
update(2 * nod + 1, mij + 1, dr, poz, val);
aint[nod] = max(aint[2 * nod], aint[2 * nod + 1]);
}
int ans = 0;
void query (int nod, int st, int dr, int a, int b) {
if (a <= st && dr <= b) {
ans = max(ans, aint[nod]);
return;
}
int mij = (st + dr) / 2;
if (a <= mij)
query(2 * nod, st, mij, a, b);
if (b > mij)
query(2 * nod + 1, mij + 1, dr, a, b);
}
int nr = 0;
void reset () {
for (int i = 1; i <= 4*nr; i++)
aint[i] = 0;
}
int main()
{
cin >> n >> x;
for (int i = 1; i <= n; i++) {
cin >> v[i];
aux.push_back(v[i] + x);
aux.push_back(v[i] - x);
aux.push_back(v[i]);
}
sort(aux.begin(), aux.end());
for (int i = 0; i < aux.size(); i++)
if (i == 0 || aux[i] != aux[i - 1]) {
aux[nr++] = aux[i];
mp[aux[nr - 1]] = nr;
}
int sol = 0;
for (int i = 1; i <= n; i++) {
ans = 0;
query(1, 1, nr, 1, mp[v[i]] - 1);
pref[i] = ans + 1;
update(1, 1, nr, mp[v[i]], pref[i]);
sol = max(ans, pref[i]);
}
reset();
for (int i = n; i >= 1; i--) {
ans = 0;
query(1, 1, nr, 1, mp[v[i]] + 1);
suf[i] = ans + 1;
update(1, 1, nr, mp[v[i]], suf[i]);
}
reset();
for (int i = 1; i <= n; i++) {
ans = 0;
query(1, 1, nr, 1, mp[v[i] + x]);
sol = max(suf[i] + ans, sol);
update(1, 1, nr, mp[v[i]], pref[i]);
}
reset();
for (int i = n; i >= 1; i--) {
ans = 0;
query(1, 1, nr, 1, mp[v[i] - x] + 1);
sol = max(sol, ans + pref[i]);
update(1, 1, nr, mp[v[i]], suf[i]);
}
cout << sol << "\n";
return 0;
}
Compilation message
glo.cpp: In function 'int main()':
glo.cpp:56:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (int i = 0; i < aux.size(); i++)
| ~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
464 ms |
262148 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
301 ms |
10348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
646 ms |
20472 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |