Submission #344157

#TimeUsernameProblemLanguageResultExecution timeMemory
344157NurlykhanHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
0 / 100
1574 ms71616 KiB
#include <bits/stdc++.h> using namespace std; const int N = (int)1e6 + 10; const int K = 450; int n, m; int w[N]; int ans[N]; int L[N], R[N], k[N]; vector<int> query[N]; int suff_w[N], suff_mood[N]; void solve(int l = 0, int r = n - 1) { if (l == r) return; int mid = (l + r) / 2; // 5 4 100 vector<int> s; // TODO: replace set with fenwick suff_w[mid + 1] = suff_mood[mid + 1] = 0; for (int i = mid; i >= l; i--) { suff_w[i] = max(suff_w[i + 1], w[i]); suff_mood[i] = suff_mood[i + 1]; while (!s.empty() && s.back() < w[i]) { suff_mood[i] = max(suff_mood[i], s.back() + w[i]); s.pop_back(); } if (s.empty() || s.back() > w[i]) s.push_back(w[i]); } s.clear(); int mx = 0, mxx = 0; for (int i = mid + 1; i <= r; i++) { if (mxx <= w[i]) { mxx = w[i]; } else { mx = max(mx, mxx + w[i]); } while (!s.empty() && s.back() < w[i]) s.pop_back(); if (s.empty() || s.back() < w[i]) s.push_back(w[i]); // TODO: optimize iteration over queries for (auto j : query[i]) { if (L[j] >= l && L[j] <= mid) { int cur_mx = max(suff_mood[L[j]], mx); int tmp = suff_w[L[j]]; int it = lower_bound(s.begin(), s.end(), tmp) - s.begin() - 1; if (it >= 0) { cur_mx = max(cur_mx, s[it] + tmp); } if (k[j] >= cur_mx) { ans[j] = 1; } else { ans[j] = 0; } } } } solve(l, mid); solve(mid + 1, r); } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) { scanf("%d", &w[i]); } for (int i = 0; i < m; i++) { scanf("%d%d%d", &L[i], &R[i], &k[i]); --L[i], --R[i]; query[R[i]].push_back(i); } solve(); for (int i = 0; i < m; i++) { if (L[i] == R[i]) ans[i] = 1; printf("%d\n", ans[i]); } return 0; }

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |         scanf("%d", &w[i]);
      |         ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |         scanf("%d%d%d", &L[i], &R[i], &k[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...