This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 - 1]) << 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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |