# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
520630 | 2022-01-30T11:40:25 Z | idas | Global Warming (CEOI18_glo) | C++11 | 51 ms | 4744 KB |
#include <bits/stdc++.h> #define FOR(i, begin, end) for(int i = (begin); i < (end); i++) #define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr) #define f first #define s second #define pb push_back #define sz(x) ((int)((x).size())) #define le(vec) vec[vec.size()-1] #define all(x) (x).begin(), (x).end() #define TSTS int ttt; cin >> ttt; while(ttt--) solve() using namespace std; typedef pair<int, int> pii; typedef pair<long long, long long> pll; typedef pair<long double, long double> pdd; typedef map<int, int> mii; typedef vector<int> vi; typedef long double ld; typedef long long ll; const int INF=1e9, MOD=1e9+7, mod=998244353; const ll LINF=1e18; void setIO() { FAST_IO; } void setIO(string s) { FAST_IO; freopen((s+".in").c_str(), "r", stdin); freopen((s+".out").c_str(), "w", stdout); } const int N=2e5+10; int n, x, a[N], ans[N]; int main() { setIO(); cin >> n >> x; FOR(i, 0, n) cin >> a[i]; vi lds; for(int i=n-1; i>=0; i--){ int l=-1, r=sz(lds)-1; while(l<r){ int m=(l+r+1)/2; if(lds[m]>a[i]-x) l=m; else r=m-1; } ans[i]=l+2; l=0, r=sz(lds); while(l<r){ int m=(l+r)/2; if(lds[m]>a[i]) l=m+1; else r=m; } if(l==sz(lds)) lds.pb(a[i]); else lds[l]=a[i]; } vi lis; int mx=0; FOR(i, 0, n) { int in=lower_bound(all(lis), a[i])-lis.begin(); if(in==sz(lis)) lis.pb(a[i]); else lis[in]=a[i]; mx=max(mx, sz(lis)+ans[i]); } cout << mx-1; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 320 KB | Output is correct |
3 | Incorrect | 1 ms | 204 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 320 KB | Output is correct |
3 | Incorrect | 1 ms | 204 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 320 KB | Output is correct |
3 | Incorrect | 1 ms | 204 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 51 ms | 3696 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 13 ms | 1100 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 20 ms | 2056 KB | Output is correct |
2 | Correct | 27 ms | 2016 KB | Output is correct |
3 | Correct | 45 ms | 3700 KB | Output is correct |
4 | Correct | 30 ms | 4084 KB | Output is correct |
5 | Correct | 14 ms | 2168 KB | Output is correct |
6 | Correct | 22 ms | 4076 KB | Output is correct |
7 | Correct | 29 ms | 4744 KB | Output is correct |
8 | Correct | 18 ms | 1984 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 320 KB | Output is correct |
3 | Incorrect | 1 ms | 204 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |