#include <bits/stdc++.h>
using namespace std;
struct node {
int cnt;
node *l, *r;
node(): cnt(0), l(nullptr), r(nullptr) {}
node(int cnt): cnt(cnt), l(nullptr), r(nullptr) {}
node(node *l, node *r): cnt(0), l(l), r(r) {
if (l) cnt += l->cnt;
if (r) cnt += r->cnt;
}
};
typedef node * pnode;
const int maxn = 1e6+3, maxm = 1e6+3, maxw = 1e9+3;
int n, m;
pair<int, int> w[maxn];
map<int, int> mp1;
int mp2[maxn];
pnode roots[maxn];
int mx[4*maxn], mxsum[4*maxn];
pnode build1(int l, int r) {
if (l == r) return new node();
int mid = (l+r)/2;
return new node(build1(l, mid), build1(mid+1, r));
}
pnode update1(pnode p, int l, int r, int pos) {
if (l == r) return new node(p->cnt + 1);
int mid = (l+r)/2;
if (pos <= mid) return new node(update1(p->l, l, mid, pos), p->r);
return new node(p->l, update1(p->r, mid+1, r, pos));
}
int query1(pnode pl, pnode pr, int l, int r, int k) {
if (l > k || pr->cnt - pl->cnt == 0) return -1;
if (l == r) return l;
int mid = (l+r)/2;
if (r <= k) {
if (pr->r->cnt - pl->r->cnt > 0) return query1(pl->r, pr->r, mid+1, r, k);
if (pr->l->cnt - pl->l->cnt > 0) return query1(pl->l, pr->l, l, mid, k);
return -1;
}
return max(query1(pl->l, pr->l, l, mid, k), query1(pl->r, pr->r, mid+1, r, k));
}
void build2(int l, int r, int v) {
if (l == r) {
mxsum[v] = -1;
mx[v] = w[l].first;
} else {
int mid = (l+r)/2;
build2(l, mid, v*2);
build2(mid+1, r, v*2+1);
int mxr = query1(roots[mid+1], roots[r+1], 0, mp1.size()-1, mp1[mx[v*2]]);
mxsum[v] = max({mxsum[v*2], mxsum[v*2+1], (mxr == -1 ? -1 : mx[v*2] + mp2[mxr])});
mx[v] = max(mx[v*2], mx[v*2+1]);
}
}
pair<int, int> query(int l, int r, int v, int lb, int rb) {
if (r < lb || l > rb) return make_pair(-1, -1);
if (l >= lb && r <= rb) return make_pair(mx[v], mxsum[v]);
int mid = (l+r)/2;
auto resl = query(l, mid, v*2, lb, rb);
auto resr = query(mid+1, r, v*2+1, lb, rb);
int mxr = -1;
if (resl.first != -1 && mid+1 <= rb) mxr = query1(roots[mid+1], roots[rb+1], 0, mp1.size()-1, mp1[resl.first]);
return make_pair(max(resl.first, resr.first), max({
resl.second,
resr.second,
(mxr == -1 ? -1 : resl.first + mp2[mxr])
}));
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for (int i=0; i<n; i++) {
cin >> w[i].first;
w[i].second = i;
}
sort(w, w+n);
for (int l=0, i=0; l<n; i++) {
int r = l;
while (r < n && w[l].first == w[r].first) r++;
mp1[w[l].first] = i;
mp2[i] = w[l].first;
l = r;
}
sort(w, w+n, [](const pair<int, int> &pa, const pair<int, int> &pb) {
return pa.second < pb.second;
});
roots[0] = build1(0, mp1.size()-1);
for (int i=1; i<=n; i++) roots[i] = update1(roots[i-1], 0, mp1.size()-1, mp1[w[i-1].first]);
build2(0, n-1, 1);
for (int i=0; i<n; i++) {
for (int j=i; j<n; j++) {
cout << i << ' ' << j << ' ' << query(0, n-1, 1, i, j).second << '\n';
}
}
while (m--) {
int l, r, k;
cin >> l >> r >> k;
cout << (query(0, n-1, 1, l-1, r-1).second <= k) << '\n';
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1058 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3058 ms |
56904 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
