제출 #276005

#제출 시각아이디문제언어결과실행 시간메모리
276005HeheheGlobal Warming (CEOI18_glo)C++14
100 / 100
76 ms5108 KiB
#include<bits/stdc++.h> //:3 using namespace std; typedef long long ll; #define all(a) (a).begin(), (a).end() #define ff first #define ss second #define pb push_back #define mp make_pair #define pi pair<int, int> #define sz(x) (int)((x).size()) //#define int long long const int dx[] = {0, 1, 0, -1}; const int dy[] = {1, 0, -1, 0}; const ll inf = 2e9; const ll mod = 1e9 + 7; const int N = 2e6 + 11; const ll INF64 = 3e18 + 1; const double eps = 1e-14; const double PI = acos(-1); //ifstream in(".in"); //ofstream out(".out"); int n, m, a[N], x, len[N]; void solve(){ cin >> n >> x; vector<int> high; for(int i = 1; i <= n; i++){ cin >> a[i]; auto it = lower_bound(all(high), a[i]); if(it == high.end()){ high.push_back(a[i]); len[i] = sz(high); continue; } high[it - high.begin()] = a[i]; len[i] = it - high.begin() + 1; } int ans = 0; vector<int> LSD; for(int i = n; i > 0; i--){ auto it = lower_bound(all(LSD), -a[i]); ans = (it == LSD.end() ? max(ans, len[i] + sz(LSD)) : max(ans, len[i] + (int)(it - LSD.begin()))); auto it1 = lower_bound(all(LSD), -a[i] - x); if(it1 == LSD.end())LSD.push_back(-a[i] - x);else LSD[it1 - LSD.begin()] = -a[i] - x; } cout << ans << '\n'; } int32_t main(){ ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << setprecision(6) << fixed; int T = 1; //cin >> T; while(T--){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...