This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//-------------dilanyan------------\\
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
//------------------KarginDefines--------------------\\
#define ll long long
#define pb push_back
#define all(u) (u).begin(), (u).end()
#define pqueue priority_queue
#define upper upper_bound
#define lower lower_bound
#define umap unordered_map
#define uset unordered_set
#define Kargin ios_base::sync_with_stdio(false);cin.tie(NULL);
#define Usaco freopen(".in", "r", stdin); freopen(".out", "w", stdout);
//-------------------KarginConstants------------------\\
const ll mod = 1000000007;
const ll inf = 1e9 + 10;
//-------------------KarginCode------------------------\\
const int N = 1000005;
int w[N];
int n, m;
struct query {
int l, r, k;
};
query q[N];
struct segtree_sort {
int size = 1;
struct node {
bool sorted = true, valid = false;
int l = 0, r = 0;
};
node z;
vector<node> tree;
void init() {
while (size < n) size <<= 1;
tree.resize(2 * size);
build(0, 0, size);
}
node merge(node b, node c) {
node a;
if (!b.valid && !c.valid) {
a.valid = false;
return a;
}
if (!c.valid) a = b;
else {
a.valid = true;
if (!b.sorted || !c.sorted) {
a.sorted = false;
return a;
}
if (b.r <= c.l) {
a.sorted = true;
a.l = b.l, a.r = c.r;
}
else a.sorted = false;
}
return a;
}
void build(int x, int lx, int rx) {
if (rx - lx == 1) {
tree[x].valid = false;
if (lx < n) {
tree[x].valid = tree[x].sorted = true;
tree[x].l = tree[x].r = w[lx];
}
return;
}
int m = (lx + rx) / 2;
build(2 * x + 1, lx, m);
build(2 * x + 2, m, rx);
tree[x] = merge(tree[2 * x + 1], tree[2 * x + 2]);
}
node get(int l, int r, int x, int lx, int rx) {
if (lx >= r || rx <= l) return z;
if (lx >= l && rx <= r) return tree[x];
int m = (lx + rx) / 2;
node getl = get(l, r, 2 * x + 1, lx, m),
getr = get(l, r, 2 * x + 2, m, rx);
node get0 = merge(getl, getr);
return get0;
}
bool get(int l, int r) {
return get(l, r, 0, 0, size).sorted;
}
};
void KarginSolve() {
cin >> n >> m;
int mn = inf;
for (int i = 0;i < n;i++) cin >> w[i], mn = min(mn, w[i]);
bool case3 = true;
for (int i = 0;i < m;i++) {
cin >> q[i].l >> q[i].r >> q[i].k;
q[i].l--;
if (q[i].k >= mn) case3 = false;
}
if (n <= 5000 && m <= 5000) {
for (int i = 0;i < m;i++) {
int ans = 1, cur = w[q[i].l];
for (int j = q[i].l;j < q[i].r - 1;j++) {
if (cur > w[j + 1]) {
if (cur + w[j + 1] > q[i].k) {
ans = 0;
break;
}
}
else cur = w[j + 1];
}
cout << ans << '\n';
}
}
else if (case3) {
segtree_sort st;
st.init();
for (int i = 0;i < m;i++) {
if (st.get(q[i].l, q[i].r)) cout << 1 << endl;
else cout << 0 << endl;
}
}
}
int main() {
//Usaco
Kargin;
int test = 1;
//cin >> test;
while (test--) {
KarginSolve();
}
return 0;
}
Compilation message (stderr)
sortbooks.cpp:1:1: warning: multi-line comment [-Wcomment]
1 | //-------------dilanyan------------\\
| ^
sortbooks.cpp:8:1: warning: multi-line comment [-Wcomment]
8 | //------------------KarginDefines--------------------\\
| ^
sortbooks.cpp:22:1: warning: multi-line comment [-Wcomment]
22 | //-------------------KarginConstants------------------\\
| ^
sortbooks.cpp:27:1: warning: multi-line comment [-Wcomment]
27 | //-------------------KarginCode------------------------\\
| ^
# | 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... |