Submission #860042

#TimeUsernameProblemLanguageResultExecution timeMemory
860042AlfraganusHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
64 / 100
1373 ms67744 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); int mn = 1e9; for (int &x : a) cin >> x, mn = min(mn, x); vector<pair<pair<int, int>, int>> que(q); bool sub3 = 1; for (int i = 0; i < q; i++){ cin >> que[i].first.first >> que[i].first.second >> que[i].second; sub3 &= (que[i].second < mn); } if(sub3){ vector<int> dp(n); for (int i = 0; i < n - 1; i++) dp[i + 1] = a[i + 1] < a[i]; for (int i = 1; i < n; i++) dp[i] += dp[i - 1]; for(int i = 0; i < q; i ++) cout << (dp[que[i].first.first - 1] == dp[que[i].first.second]) << endl; return 0; } tree.resize(n << 2); build(1, 1, n); for (int i = 0, l, r, k; i < q; i++) { l = que[i].first.first, r = que[i].first.second, k = que[i].second; 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:97:17: warning: unused variable 'x' [-Wunused-variable]
   97 |             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...