#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define ALL(x) x.begin(),x.end()
using namespace std;
using PII = pair <int, int>;
using VI = vector <int>;
using VVI = vector <VI>;
using VPI = vector <PII>;
struct Node {
int max, max1, maxInv;
Node() {
max = max1 = -1;
maxInv = -1;
}
};
const int N = 1e6 + 5;
const int M = 4 * N;
int n, m;
VPI addNum;
int nums[N], queries[N], K[N];
Node node[M];
void build(int l, int r, int head) {
if (l == r) {
node[head].max = nums[l];
return;
}
int mid = (l+r)>>1;
build(l, mid, head*2+1);
build(mid+1, r, head*2+2);
node[head].max = max(node[head*2+1].max, node[head*2+2].max);
int curMax = nums[l];
for (int i = l+1; i <= r; i++) {
if (nums[i] >= curMax) curMax = nums[i];
else node[head].maxInv = max(node[head].maxInv, curMax+nums[i]);
}
}
void update(int l, int r, int id, int val, int head) {
if (l == r) {
node[head].max1 = val;
return;
}
int mid = (l+r)>>1;
if (id <= mid) update(l, mid, id, val, head*2+1);
else update(mid+1, r, id, val, head*2+2);
node[head].max1 = max(node[head*2+1].max1, node[head*2+2].max1);
}
int query(int l, int r, int L, int R, int head) {
if (l > R || L > r) return -1;
if (L <= l && r <= R)
return node[head].max1;
int mid = (l+r)>>1;
return max(
query(l, mid, L, R, head*2+1),
query(mid+1, r, L, R, head*2+2)
);
}
set <VI> allCheck;// lMax, id, mid, r, head;
int dfs(int l, int r, int L, int R, int id, int head) { // return insideMax;
if (L <= l && r <= R) {
queries[id] = max(queries[id], node[head].maxInv);
return node[head].max;
}
int mid = (l+r)>>1;
if (R <= mid) return dfs(l, mid, L, R, id, head*2+1);
if (mid+1 <= L) return dfs(mid+1, r, L, R, id, head*2+2);
int lMax = dfs(l, mid, L, R, id, head*2+1);
int rMax = dfs(mid+1, r, L, R, id, head*2+2);
allCheck.insert({lMax, id, mid+1, r, L, R, head*2+2});
return max(lMax, rMax);
}
signed main() {
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> nums[i];
addNum.pb({nums[i], i});
}
// build(1, n, 0);
sort(ALL(addNum));
memset(queries, -1, sizeof(queries));
// for (int i = 1; i <= m; i++) {
// int l, r, k; cin >> l >> r >> k;
// K[i] = k;
// dfs(1, n, l, r, i, 0);
// }
// int addId = 0, lMax, id, L, R, mid, r, head;
// while(!allCheck.empty()) {
// auto it = allCheck.begin();
// VI tmp = *it;
// allCheck.erase(it);
// lMax = tmp[0];
// id = tmp[1];
// mid = tmp[2];
// r = tmp[3];
// L = tmp[4];
// R = tmp[5];
// head = tmp[6];
// while (addId < addNum.size() && lMax > addNum[addId].ff) {
// int num, I;
// tie(num, I) = addNum[addId++];
// update(1, n, I, num, 0);
// }
// int rMax = query(mid, r, L, R, head);
// int cur = (rMax == -1 ? -1 : lMax+rMax);
// queries[id] = max(queries[id], cur);
// cout << "UPdate: " << id << ' ' << cur << ' ' << lMax << ' ' << rMax << ' ' << mid << ' ' << r << '\n';
// }
// for (int i = 1; i <= m; i++)
// cout << queries[i] << ' ' << K[i] << '\n';
for (int i = 1; i <= m; i++)
cout << (queries[i] <= K[i] ? 1 : 0) << '\n';
}
Compilation message
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:75:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
75 | freopen("in.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:76:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | freopen("out.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
24 ms |
51148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
24 ms |
51148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
21 ms |
51148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
23 ms |
51084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
24 ms |
51148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
24 ms |
51148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
