#include <bits/stdc++.h>
#define N 1000005
using namespace std;
int a[N];
int ans[N];
struct node{
int val = 0,maxi = -1;
};
struct node2{
int l = 0,r = 0, val = 0;
}tree[N*20];
vector<pair<int,int>> roots;
int cnt = 1;
int upd(int v,int tl,int tr,int pos,int val){
if(tl == tr){
int nw = ++cnt;
tree[nw].val = tree[v].val + val;
return nw;
}
int tm = (tl + tr)/2;
if(pos <= tm){
int nw = ++cnt;
tree[nw].l = upd(tree[v].l,tl,tm,pos,val);
tree[nw].r = tree[v].r;
tree[nw].val = tree[tree[nw].l].val + tree[tree[nw].r].val;
return nw;
}
else{
int nw = ++cnt;
tree[nw].l = tree[v].l;
tree[nw].r = upd(tree[v].r,tm+1,tr,pos,val);
tree[nw].val = tree[tree[nw].l].val + tree[tree[nw].r].val;
return nw;
}
}
int gett(int v,int tl,int tr,int l,int r){
if(r < tl || tr < l){
return 0;
}
if(l <= tl && tr <= r){
return tree[v].val;
}
int tm = (tl + tr)/2;
return gett(tree[v].l,tl,tm,l,r) + gett(tree[v].r,tm+1,tr,l,r);
}
struct SegTree{
vector<node> t;
int n;
int k;
SegTree(int sz){
n = sz;
t.assign(4*n,{0,-1});
build(1,1,n);
}
node merge(node a,node b){
node ret;
ret.val = max(a.val,b.val);
ret.maxi = max(a.maxi,b.maxi);
return ret;
}
void build(int v,int tl,int tr){
if(tl == tr){
t[v].maxi = a[tl];
return;
}
int tm = (tl + tr)/2;
build(v*2,tl,tm);
build(v*2+1,tm+1,tr);
t[v] = merge(t[v*2],t[v*2+1]);
for(int i = tm+1;i<=tr;i++){
if(a[i] < t[v*2].maxi){
t[v].val = max(t[v].val,t[v*2].maxi + a[i]);
}
}
}
node get(int v,int tl,int tr,int l,int r){
if(tr < l || r < tl){
return {0,-1};
}
if(l <= tl && tr <= r){
return t[v];
}
int tm = (tl + tr)/2;
node a = get(v*2,tl,tm,l,r);
node b = get(v*2+1,tm+1,tr,l,r);
int num = k+1 - a.maxi;
if(num < a.maxi){
int cnt = 0;
int idx = lower_bound(roots.begin(),roots.end(),make_pair(num,0),greater<pair<int,int>>()) - roots.begin();
if(idx != roots.size())
cnt += gett(roots[idx].second,1,n,max(l,tm+1),min(r,tr));
idx = lower_bound(roots.begin(),roots.end(),make_pair(a.maxi,0),greater<pair<int,int>>()) - roots.begin();
if(idx != roots.size())
cnt -= gett(roots[idx].second,1,n,max(l,tm+1),min(r,tr));
if(cnt)
a.val = k+1;
}
return merge(a,b);
}
node get(int l,int r,int kk){
k = kk;
return get(1,1,n,l,r);
}
};
struct SegTree2{
vector<int> t;
int n;
SegTree2(int sz){
n = sz;
t.assign(4*n,1e9);
}
void upd(int v,int tl,int tr,int pos,int val){
if(tl == tr){
t[v] = min(t[v],val);
return;
}
int tm = (tl + tr)/2;
if(pos <= tm){
upd(v*2,tl,tm,pos,val);
}
else upd(v*2+1,tm+1,tr,pos,val);
t[v] = min(t[v*2],t[v*2+1]);
}
int get(int v,int tl,int tr,int l,int r){
if(tr < l || r < tl){
return 1e9;
}
if(l <= tl && tr <= r){
return t[v];
}
int tm = (tl + tr)/2;
return min(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
}
void upd(int pos,int val){
upd(1,1,n,pos,val);
}
int get(int l,int r){
return get(1,1,n,l,r);
}
};
void solve(){
int n,m;
cin >> n >> m;
vector<int> cmp;
for(int i = 1;i<=n;i++){
cin >> a[i];
cmp.push_back(i);
}
sort(cmp.begin(),cmp.end(),[&](int x,int y){
return a[x] > a[y];
});
roots.push_back({-1,1});
for(auto u:cmp){
int tmp = roots.back().second;
if(roots.back().first == u)
roots.pop_back();
roots.push_back({a[u],upd(tmp,1,n,u,1)});
}
SegTree t(n);
for(int i = 1;i<=m;i++){
int l,r,k;
cin >> l >> r >> k;
ans[i] = t.get(l,r,k).val <= k;
}
for(int i = 1;i<=m;i++){
cout << ans[i] << '\n';
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef Local
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t=1;
//cin>>t;
while(t--){
solve();
}
#ifdef Local
cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
#endif
}
Compilation message
sortbooks.cpp: In member function 'node SegTree::get(int, int, int, int, int)':
sortbooks.cpp:90:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | if(idx != roots.size())
| ~~~~^~~~~~~~~~~~~~~
sortbooks.cpp:93:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | if(idx != roots.size())
| ~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1167 ms |
262144 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
695 ms |
26476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
