# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
282765 | 2020-08-24T22:02:07 Z | doowey | Global Warming (CEOI18_glo) | C++14 | 68 ms | 8748 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pii; #define fi first #define se second #define mp make_pair #define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const ll inf = (ll)1e10; int main(){ fastIO; int n; ll x; cin >> n >> x; vector<ll> v(n); for(int i = 0 ; i < n; i ++ ){ cin >> v[i]; } vector<int> g; vector<pii> nx; int res = 1; int mid, l, r; int sh; for(int i = n-1; i >= 0 ; i -- ){ sh = v[i]; l = 0, r = (int)g.size(); while(l < r){ mid = (l + r) / 2; if(g[mid] <= sh) r = mid; else l = mid + 1; } if(l == g.size()){ nx.push_back(mp(sh, -1)); g.push_back(sh); } else{ nx.push_back(mp(g[l], l)); g[l]=sh; } } vector<int> cc; int nl, nr; int id; for(int i = 0 ; i < n; i ++ ){ if(nx.back().se == -1){ g.pop_back(); } else{ g[nx.back().se] = nx.back().fi; } nx.pop_back(); sh = v[i]-x; l=0,r=cc.size(); while(l < r){ mid = (l + r) / 2; if(cc[mid] < sh) l = mid + 1; else r = mid; } id = l; if(id == cc.size()){ cc.push_back(sh); } else{ cc[id] = sh; } l = 0, r = g.size(); while(l + 1 < r){ mid = (l + r) / 2; if(g[mid] > sh) l = mid; else r = mid; } res = max(res, (id+1)+l+(g[l]>sh)); } cout << res << "\n"; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Incorrect | 0 ms | 384 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Incorrect | 0 ms | 384 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Incorrect | 0 ms | 384 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 67 ms | 6136 KB | Output is correct |
2 | Correct | 67 ms | 8048 KB | Output is correct |
3 | Correct | 68 ms | 8048 KB | Output is correct |
4 | Correct | 68 ms | 8048 KB | Output is correct |
5 | Correct | 41 ms | 7700 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 1920 KB | Output is correct |
2 | Correct | 16 ms | 2432 KB | Output is correct |
3 | Correct | 16 ms | 2432 KB | Output is correct |
4 | Correct | 10 ms | 2204 KB | Output is correct |
5 | Correct | 0 ms | 384 KB | Output is correct |
6 | Correct | 10 ms | 2204 KB | Output is correct |
7 | Correct | 14 ms | 2432 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 27 ms | 3324 KB | Output is correct |
2 | Correct | 28 ms | 4348 KB | Output is correct |
3 | Correct | 60 ms | 8048 KB | Output is correct |
4 | Correct | 43 ms | 7780 KB | Output is correct |
5 | Correct | 28 ms | 3984 KB | Output is correct |
6 | Correct | 43 ms | 7532 KB | Output is correct |
7 | Correct | 49 ms | 8748 KB | Output is correct |
8 | Correct | 24 ms | 4348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Incorrect | 0 ms | 384 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |