Submission #739656

#TimeUsernameProblemLanguageResultExecution timeMemory
739656asdfgraceGlobal Warming (CEOI18_glo)C++17
62 / 100
45 ms6220 KiB
#include <bits/stdc++.h> using namespace std; #define DEBUG(x) //x #define A(x) DEBUG(assert(x)) #define PRINT(x) DEBUG(cerr << x) #define PV(x) DEBUG(cerr << #x << " = " << x << '\n') #define PV2(x) DEBUG(cerr << #x << " = " << x.first << ',' << x.second << '\n') #define PAR(x) DEBUG(PRINT(#x << " = { "); for (auto y : x) PRINT(y << ' '); PRINT("}\n");) #define PAR2(x) DEBUG(PRINT(#x << " = { "); for (auto [y, z] : x) PRINT(y << ',' << z << " "); PRINT("}\n");) typedef int64_t i64; const int INF = 1000000007; //998244353; struct S { int n, k; vector<int> a, b; void run() { cin >> n >> k; a.resize(n); b.resize(n, k); for (int i = 0; i < n; ++i) { cin >> a[i]; b[i] += a[i]; } reverse(b.begin(), b.end()); PAR(a); PAR(b); vector<int> lis; vector<pair<int, int>> dpa(n); // {location, old val} for (int i = 0; i < n; ++i) { int pos = lower_bound(lis.begin(), lis.end(), a[i]) - lis.begin(); if (pos == lis.size()) { dpa[i] = {pos, -1}; lis.push_back(a[i]); } else { dpa[i] = {pos, lis[pos]}; lis[pos] = a[i]; } } PAR(lis); reverse(dpa.begin(), dpa.end()); PAR2(dpa); int ans = lis.size(); vector<int> lds; for (int i = 0; i < n; ++i) { lis[dpa[i].first] = dpa[i].second; if (lis[dpa[i].first] == -1) lis.pop_back(); // find first element smaller than b[i] int pos = lower_bound(lds.begin(), lds.end(), -b[i]) - lds.begin(); PV(pos); if (pos == lds.size()) { lds.push_back(-b[i]); } else { lds[pos] = -b[i]; } int bad = (lis.size() ? lds.end() - lower_bound(lds.begin(), lds.end(), -lis.back()) : 0); PV(bad); ans = max(ans, int(lis.size() + lds.size() - bad)); PAR(lis); PAR(lds); PV(ans); } cout << ans << '\n'; } }; int main() { ios::sync_with_stdio(0); cin.tie(0); auto sol = make_unique<S>(); sol->run(); }

Compilation message (stderr)

glo.cpp: In member function 'void S::run()':
glo.cpp:33:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |       if (pos == lis.size()) {
      |           ~~~~^~~~~~~~~~~~~
glo.cpp:54:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |       if (pos == lds.size()) {
      |           ~~~~^~~~~~~~~~~~~
#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...