# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1000084 | daffuwu | Global Warming (CEOI18_glo) | C++14 | 46 ms | 3712 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, x, t[200069], ans, r[200069];
vector<int> vc;
int main()
{
int i, j;
scanf("%d%d", &n, &x);
for (i=1; i<=n; i++)
{
scanf("%d", t+i);
}
for (i=n; i>=1; i--)
{
auto it = lower_bound(vc.begin(), vc.end(), -t[i]);
if (it == vc.end())
{
vc.push_back(-t[i]);
r[i] = vc.size();
} else
{
*it = -t[i];
r[i] = it-vc.begin()+1;
}
}
vc.clear();
for (i=1; i<=n; i++)
{
auto it = lower_bound(vc.begin(), vc.end(), t[i]);
if (it == vc.end()) vc.push_back(t[i]);
else *it = t[i];
j = upper_bound(vc.begin(), vc.end(), t[i+1]+x-1)-vc.begin();
ans = max(ans, j+r[i+1]);
}
printf("%d\n", ans);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |