제출 #518469

#제출 시각아이디문제언어결과실행 시간메모리
518469Yazan_AlattarGlobal Warming (CEOI18_glo)C++14
100 / 100
623 ms74944 KiB
#include <iostream> #include <fstream> #include <vector> #include <cstring> #include <algorithm> #include <set> #include <map> #include <queue> #include <list> #include <utility> #include <cmath> #include <numeric> #include <assert.h> using namespace std; typedef long long ll; #define F first #define S second #define pb push_back #define endl "\n" #define all(x) x.begin(), x.end() const int M = 300007; const ll inf = 1e9; const ll mod = 1e9 + 7; const double pi = acos(-1); const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1}; int n, x, a[M], pref[M], suf[M], last[M], seg[32 * M], L[32 * M], R[32 * M], ans, nodesNum = 1; map <int,int> lastocur; void upd(int pos, int v, int node = 1, int l = 1, int r = 1e9 + 1) { if(l == r){ seg[node] = v; return; } int mid = (l + r) / 2; if(pos <= mid){ if(!L[node]) L[node] = ++nodesNum; upd(pos, v, L[node], l, mid); } else{ if(!R[node]) R[node] = ++nodesNum; upd(pos, v, R[node], mid + 1, r); } seg[node] = max(seg[L[node]], seg[R[node]]); return; } int get(int st, int en, int node = 1, int l = 1, int r = 1e9 + 1) { if(l > en || r < st) return -inf; if(l >= st && r <= en) return seg[node]; if(!L[node]) L[node] = ++nodesNum; if(!R[node]) R[node] = ++nodesNum; int mid = (l + r) / 2; return max(get(st, en, L[node], l, mid), get(st, en, R[node], mid + 1, r)); } int main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> x; for(int i = 1; i <= n; ++i) cin >> a[i]; vector <int> lis; for(int i = 1; i <= n; ++i){ int it = lower_bound(all(lis), a[i]) - lis.begin(); if(it == lis.size()) lis.pb(a[i]); else lis[it] = a[i]; pref[i] = it + 1; } ans = lis.size(); lis.clear(); for(int i = n; i; --i){ int it = lower_bound(all(lis), - a[i]) - lis.begin(); if(it == lis.size()) lis.pb(-a[i]); else lis[it] = -a[i]; suf[i] = it + 1; upd(a[i], it + 1); if(lastocur[a[i]]) last[i] = lastocur[a[i]]; lastocur[a[i]] = i; } for(int i = 1; i <= n; ++i){ upd(a[i], suf[last[i]]); ans = max(ans, pref[i] + get(max(1, a[i] - x + 1), 1e9 + 1)); } cout << ans << endl; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

glo.cpp: In function 'int main()':
glo.cpp:68:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         if(it == lis.size()) lis.pb(a[i]);
      |            ~~~^~~~~~~~~~~~~
glo.cpp:76:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         if(it == lis.size()) lis.pb(-a[i]);
      |            ~~~^~~~~~~~~~~~~
#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...