Submission #917645

#TimeUsernameProblemLanguageResultExecution timeMemory
917645Sense143Global Warming (CEOI18_glo)C++14
10 / 100
46 ms12492 KiB
#include <bits/stdc++.h> #define endl '\n' using namespace std; const int N = 2e5+10; int dp[N]; vector<pair<int,int>> a[N]; vector<int> keep; int main(){ // freopen("pcb.in", "r", stdin); // freopen("pcb.out", "w", stdout); ios::sync_with_stdio(false); cin.tie(0); int n,m; cin >> n >> m; int cnt = 0; for(int i=0;i<n;i++){ int temp; cin >> temp; keep.push_back(temp); int idx = lower_bound(dp, dp + cnt , temp) - dp; if(idx == cnt) cnt++; dp[idx] = temp; a[idx].push_back({temp,i}); } vector<int> ans; int idx_first, idx_last; int num = a[cnt-1][0].first; ans.push_back(num); idx_last = a[cnt-1][0].second; for(int i=cnt-2;i>=0;i--){ for(auto e:a[i]){ if(e.first < num){ num = e.first; idx_first = e.second; ans.push_back(num); break; } } } // reverse(ans.begin(), ans.end()); // for(auto e:ans){ // cout << e << " "; // }cout << endl; // cout << idx_first << " " << idx_last; for(int i=idx_first;i<=idx_last;i++){ keep[i] -= m; } cnt = 0; for(int i=0;i<keep.size();i++){ int idx = lower_bound(dp, dp + cnt, keep[i]) - dp; if(idx == cnt) cnt++; dp[idx] = keep[i]; } cout << cnt << endl; }

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i=0;i<keep.size();i++){
      |                 ~^~~~~~~~~~~~
glo.cpp:23:9: warning: 'idx_first' may be used uninitialized in this function [-Wmaybe-uninitialized]
   23 |     int idx_first, idx_last;
      |         ^~~~~~~~~
#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...