#include <chrono>
#include <random>
#include <iostream>
#include <string>
#include <unordered_map>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
using namespace std;
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
#define tm abc
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mod = 1e9 + 7;
const int inf = 1e9;
const int N = 1e6 + 15;
int n, m, a[N], maxx[N];
bool ans[N];
struct query {
int l, r, k, ind;
bool operator < (const query &b) const {
return l < b.l;
}
} qs[N];
struct node {
node *l, *r;
int key, pr, val, ind, add;
node(int key, int val, int ind) : key(key), val(val), ind(ind) {
pr = uniform_int_distribution<>(0, inf)(rng);
l = r = NULL;
add = 0;
}
};
typedef node* pnode;
pnode root = NULL;
inline void tm(int &a, int b) {
a = max(a, b);
}
inline void push(pnode &t) {
if(t) {
if(t->l) {
tm(t->l->val, t->add);
tm(t->l->add, t->add);
}
if(t->r) {
tm(t->r->val, t->add);
tm(t->r->add, t->add);
}
}
}
void split(pnode t, pnode &l, pnode &r, int key) {
if(!t)
return void(l = r = t);
push(t);
if(t->key <= key)
split(t->r, t->r, r, key), l = t;
else
split(t->l, l, t->l, key), r = t;
}
void merge(pnode &t, pnode l, pnode r) {
push(l);
push(r);
if(!l || !r)
t = l ? l : r;
else if(l->pr > r->pr)
merge(l->r, l->r, r), t = l;
else
merge(r->l, l, r->l), t = r;
}
inline void insert(pnode &t, pnode nw) {
pnode t1, t2;
split(t, t1, t2, nw->key);
merge(t1, t1, nw);
merge(t, t1, t2);
}
inline void multiupdate(pnode &t, int l, int r, int val) {
pnode t1, t2, t3, t4;
split(t, t1, t2, l - 1);
split(t2, t3, t4, r);
if(t3) {
tm(t3->val, val);
tm(t3->add, val);
}
merge(t2, t3, t4);
merge(t, t1, t2);
}
void traverse(pnode t) {
if(t) {
push(t);
maxx[t->ind] = t->val;
traverse(t->l);
traverse(t->r);
}
}
set <pii> cur;
main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
cur.insert(mp(a[i], i));
}
for(int i = 1; i <= m; ++i) {
scanf("%d%d%d", &qs[i].l, &qs[i].r, &qs[i].k);
qs[i].ind = i;
}
sort(qs + 1, qs + 1 + m);
for(int i = 1, j = 1; i <= n; ++i) {
while(j <= m && qs[j].l <= i) {
insert(root, new node(qs[j].r, 0, j));
++j;
}
set <pii>::iterator it = cur.lower_bound(mp(a[i], -inf));
pii val = mp(0, 0);
if(it != cur.begin()) {
--it;
val = mp(a[i] + it->f, it->se);
}
if(val.f)
multiupdate(root, val.se, n, val.f);
cur.erase(mp(a[i], i));
}
traverse(root);
for(int i = 1; i <= m; ++i) {
if(maxx[i] <= qs[i].k)
ans[qs[i].ind] = true;
}
for(int i = 1; i <= m; ++i)
puts(ans[i] ? "1" : "0");
return 0;
}
Compilation message
sortbooks.cpp:137:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:138:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:140:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
sortbooks.cpp:144:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &qs[i].l, &qs[i].r, &qs[i].k);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3023 ms |
73588 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
571 ms |
9692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
