Submission #863553

#TimeUsernameProblemLanguageResultExecution timeMemory
863553prohackerGlobal Warming (CEOI18_glo)C++14
0 / 100
144 ms9316 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double using namespace std; const int N = 2e5+10; const int INF = INT_MAX; const int mod = 1e9+7; int a[N],n,r[N],bit[4*N]; int m; vector<int> pos = {}; int b[N],ans; void pre_calc() { for(int i = 0 ; i <= n ; i++) { pos.push_back(a[i]+1); pos.push_back(a[i]); pos.push_back(a[i]-m+1); } sort(pos.begin(),pos.end()); pos.resize(unique(pos.begin(),pos.end())-pos.begin()); } int get_val(int x) { return lower_bound(pos.begin(),pos.end(),x)-pos.begin()+1; } void update(int id, int val) { while(id > 0) { bit[id] = max(bit[id],val); id -= (id & (-id)); } } int get(int id) { int res = 0; while(id <= N) { res = max(res,bit[id]); id += (id & (-id)); } return res; } signed main() { if (fopen("GLO.inp", "r")) { freopen("GLO.inp", "r", stdin); freopen("GLO.out", "w", stdout); } ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for(int i = 1 ; i <= n ; i++) { cin >> a[i]; } pre_calc(); for(int i = n ; i >= 0 ; i--) { int id = get_val(a[i]-m+1); r[i] = max(r[i],get(id)+1); int id2 = get_val(a[i]); id = get_val(a[i]+1); update(id2,get(id)+1); } ans = r[0]; for(int i = 1, res = 0 ; i <= n ; i++) { int id = lower_bound(b+1,b+res+1,a[i])-b; b[id] = a[i]; res = max(res,id); ans = max(ans,res+r[i]-1); } cout << ans; return 0; }

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         freopen("GLO.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
glo.cpp:50:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         freopen("GLO.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#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...