| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1267094 | GoBananas69 | Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) | C++20 | 0 ms | 0 KiB |
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
struct SegmentTree {
struct Node {
int mx, sum;
Node() : mx(0), sum(0) {}
Node(int _val) : mx(_val), sum(_val) {}
Node(int _sum, int _mx) : sum(_sum), mx(_mx) {}
Node operator+(const Node &b) const { return Node(sum + b.sum, max(mx, b.mx)); }
};
int n;
vector<int> nums;
vector<Node> tree;
int sum(int i, int L, int R, int l, int r) {
if (l > r) return 0;
if (L == l && r == R) {
return tree[i].sum;
}
int m = (L + R) / 2;
int x = 2 * i + 1, y = x + 1;
if (r <= m) {
return sum(x, L, m, l, r);
} else if (l > m) {
return sum(y, m + 1, R, l, r);
} else {
return sum(x, L, m, l, m) + sum(y, m + 1, R, m + 1, r);
}
}
int mx(int i, int L, int R, int l, int r) {
if (l > r) return -INT_MAX;
if (L == l && r == R) {
return tree[i].mx;
}
int m = (L + R) / 2;
int x = 2 * i + 1, y = x + 1;
if (r <= m) {
return mx(x, L, m, l, r);
} else if (l > m) {
return mx(y, m + 1, R, l, r);
} else {
return max(mx(x, L, m, l, m), mx(y, m + 1, R, m + 1, r));
}
}
void update_set(int i, int L, int R, int p, int v) {
if (L == R) {
tree[i] = Node(v);
return;
}
int m = (L + R) / 2;
int x = 2 * i + 1, y = x + 1;
if (p <= m) update_set(x, L, m, p, v);
else update_set(y, m + 1, R, p, v);
tree[i] = tree[x] + tree[y];
}
void build(int i, int L, int R) {
if (L == R) {
tree[i] = Node(nums[L]);
return;
}
int m = (L + R) / 2;
int x = 2 * i + 1, y = x + 1;
build(x, L, m);
build(y, m + 1, R);
tree[i] = tree[x] + tree[y];
}
SegmentTree(vector<int> _nums) : n(_nums.size()), nums(_nums) {
tree.assign(4 * max(1, n), Node());
if (n > 0) build(0, 0, n - 1);
}
int sum(int l, int r) {
if (l > r) return 0;
return sum(0, 0, n - 1, l, r);
}
int mx(int l, int r) {
if (l > r) return -INT_MAX;
return mx(0, 0, n - 1, l, r);
}
void update(int p, int v) { update_set(0, 0, n - 1, p, v); }
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
if (!(cin >> n >> m)) return 0;
vector<int> w(n);
for (int &i : w) cin >> i;
for (int _ = 0; _ < m; ++_) {
int l, r, k;
cin >> l >> r >> k;
l--;
r--;
int len = r - l + 1;
vector<int> a(len), d(len);
for (int i = l; i <= r; ++i) {
a[i - l] = w[i];
d[i - l] = w[i];
}
sort(d.begin(), d.end());
d.erase(unique(d.begin(), d.end()), d.end());
for (int &x : a) x = lower_bound(d.begin(), d.end(), x) - d.begin();
int D = (int)d.size();
SegmentTree tree(vector<int>(D, 0));
vector<int> inv(len, 0);
long long ok = 0;
for (int i = 0; i < len; ++i) {
if (a[i] + 1 <= D - 1) inv[i] = tree.sum(a[i] + 1, D - 1);
else inv[i] = 0;
ok += inv[i];
int cur = tree.sum(a[i], a[i]);
tree.update(a[i], cur + 1);
}
if (ok == 0) {
cout << "1\n";
continue;
}
int mx = -1;
int best_sum = 0;
for (int i = 0; i < len; ++i) {
mx = max(mx, d[a[i]]);
if (inv[i] > 0) {
best_sum = max(best_sum, d[a[i]] + mx);
}
}
cout << (best_sum > k ? "0\n" : "1\n");
}
return 0;
}