Submission #860041

#TimeUsernameProblemLanguageResultExecution timeMemory
860041AlfraganusHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
64 / 100
3057 ms215828 KiB
#include <bits/stdc++.h> using namespace std; struct tree_type { int s; vector<pair<int, int>> arr; }; vector<tree_type> tree; vector<int> a; const int inf = INT_MAX; void build(int v, int l, int r) { if (l == r) { tree[v].s = -1; tree[v].arr.push_back({a[l - 1], l}); } else { int m = (l + r) >> 1; build(v << 1, l, m); build(v << 1 | 1, m + 1, r); tree[v] = tree[v << 1]; tree[v].s = max(tree[v].s, tree[v << 1 | 1].s); int mx = inf; int i = 0; while (i < tree[v << 1 | 1].arr.size() && tree[v << 1 | 1].arr[i] < tree[v].arr.back()) mx = tree[v << 1 | 1].arr[i++].first; if (mx != inf) tree[v].s = max(tree[v].arr.back().first + mx, tree[v].s); while (i < tree[v << 1 | 1].arr.size()) tree[v].arr.push_back(tree[v << 1 | 1].arr[i++]); } } int get(int v, int l, int r, int L, int R, int k) { if (L == l && r == R) { if (tree[v].s > k) throw 1; return tree[v].arr.back().first; } int m = (l + r) >> 1; if (R <= m) return get(v << 1, l, m, L, R, k); else if (m < L) return get(v << 1 | 1, m + 1, r, L, R, k); else { int left = get(v << 1, l, m, L, m, k); int right = get(v << 1 | 1, m + 1, r, m + 1, R, k); if (left * 2 > k) { auto id = upper_bound(tree[v << 1 | 1].arr.begin(), tree[v << 1 | 1].arr.end(), make_pair(k - left, inf)); if (id != tree[v << 1 | 1].arr.end() && id->second <= R && left > id->first) throw 1; } return max(left, right); } } int main() { cin.tie(nullptr)->sync_with_stdio(false); int n, q; cin >> n >> q; a.resize(n); tree.resize(n << 2); for (int &x : a) cin >> x; build(1, 1, n); for (int i = 0, l, r, k; i < q; i++) { cin >> l >> r >> k; try { int x = get(1, 1, n, l, r, k); cout << "1\n"; } catch (int x) { cout << "0\n"; } } return 0; }

Compilation message (stderr)

sortbooks.cpp: In function 'void build(int, int, int)':
sortbooks.cpp:30:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         while (i < tree[v << 1 | 1].arr.size() && tree[v << 1 | 1].arr[i] < tree[v].arr.back())
      |                ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:35:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         while (i < tree[v << 1 | 1].arr.size())
      |                ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:80:17: warning: unused variable 'x' [-Wunused-variable]
   80 |             int x = get(1, 1, n, l, r, k);
      |                 ^
#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...