# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
170004 | 2019-12-23T15:06:24 Z | mhy908 | Global Warming (CEOI18_glo) | C++14 | 2000 ms | 207000 KB |
#include <bits/stdc++.h> #define pb push_back #define mp make_pair #define F first #define S second using namespace std; typedef long long LL; const LL llinf=9000000000000000000; int n; LL x, arr[200010]; vector<LL> lis, lds; int dplis[200010], dplds[200010], ans; LL minlds[200010]; pair<int, LL> change[200010]; int main() { scanf("%d %lld", &n, &x); for(int i=1; i<=n; i++)scanf("%lld", &arr[i]); for(int i=1; i<=n; i++){ auto it=lower_bound(lis.begin(), lis.end(), arr[i]); change[i]=mp(it-lis.begin(), it==lis.end()?llinf:*it); if(it==lis.end())lis.pb(arr[i]); else *it=min(arr[i], *it); dplis[i]=lower_bound(lis.begin(), lis.end(), minlds[i+1]+x)-lis.begin(); ans=max(ans, dplis[i]+dplds[i+1]); } ans=dplis[n]; arr[0]=-llinf; for(int i=n; i>=1; i--){ lis[change[i].F]=change[i].S; puts("LIS : "); for(int j=0; j<lis.size(); j++)printf("%lld ", lis[j]); puts(""); auto it=lower_bound(lds.begin(), lds.end(), -arr[i]); int temp1=it-lds.begin()+1; if(it==lds.end())lds.pb(-arr[i]); else *it=-arr[i]; int temp2=lower_bound(lis.begin(), lis.end(), arr[i]+x)-lis.begin(); ans=max(ans, temp1+temp2); } printf("%d", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2045 ms | 181724 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2045 ms | 207000 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2056 ms | 192364 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 348 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |