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 = 1e18;
//-------------------KarginCode------------------------\\
const int N = 1000005;
int w[N];
int n, m;
pair<int, int> tree[4 * N];
struct segtree {
int size = 1;
void init() {
while (size < n) size <<= 1;
build(0, 0, size);
}
void build(int x, int lx, int rx) {
if (rx - lx == 1) {
tree[x] = { -1,-1 };
if (lx < n) tree[x] = { w[lx],lx };
return;
}
int m = (lx + rx) / 2;
build(2 * x + 1, lx, m);
build(2 * x + 2, m, rx);
if (tree[2 * x + 1].first >= tree[2 * x + 2].first) tree[x] = tree[2 * x + 1];
else tree[x] = tree[2 * x + 2];
}
void set(int i, pair<int, int> v, int x, int lx, int rx) {
if (rx - lx == 1) {
tree[x] = v;
return;
}
int m = (lx + rx) / 2;
if (i < m) set(i, v, 2 * x + 1, lx, m);
else set(i, v, 2 * x + 2, m, rx);
if (tree[2 * x + 1].first >= tree[2 * x + 2].first) tree[x] = tree[2 * x + 1];
else tree[x] = tree[2 * x + 2];
}
void set(int i, pair<int,int> v) {
set(i, v, 0, 0, size);
}
pair<int, int> get(int l, int r, int x, int lx, int rx) {
if (lx >= r || rx <= l) return { -1,-1 };
if (lx >= l && rx <= r) return tree[x];
int m = (lx + rx) / 2;
pair<int, int> getl = get(l, r, 2 * x + 1, lx, m),
getr = get(l, r, 2 * x + 2, m, rx);
pair<int, int> get0;
if (getl.first >= getr.first) get0 = getl;
else get0 = getr;
return get0;
}
pair<int, int> get(int l, int r) {
return get(l, r, 0, 0, size);
}
};
void KarginSolve() {
cin >> n >> m;
for (int i = 0;i < n;i++) cin >> w[i];
if(n <= 5000 && m <= 5000) {
segtree st;
st.init();
while (m--) {
int l, r, k;
cin >> l >> r >> k;
l--;
int ans = 1;
for (int i = 0; i < r - l + 1;i++) {
pair<int, int> x = st.get(l, r);
pair<int, int> y = st.get(x.second + 1, r);
assert(x.first != -1);
if (y.first != -1) {
if (x.first + y.first > k) {
ans = 0;
break;
}
}
st.set(x.second, { -1,-1 });
}
cout << ans << '\n';
for (int i = l;i <= r;i++) st.set(i, { w[i],i });
}
}
}
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... |