This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct query{
ll x;
ll y;
ll k;
ll ind;
ll type;
};
ll wej[1000003];
vector<query> ev;
const ll base=1<<20;
ll tree[2*base];
void update(ll v, ll x){
v+=base;
if (tree[v]>=x)return;
tree[v]=x;
v>>=1;
while(v){
tree[v]=max(tree[2*v],tree[2*v+1]);
v>>=1;
}
}
ll check(ll p){
ll ans=0;
p+=base-1;
while(p/2){
if (p&1)ans=max(ans,tree[p-1]);
p>>=1;
}
return ans;
}
ll odpow[1000003];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n,m;
cin >> n >> m;
stack<pair<ll,ll>> st;
for (ll i = 1; i<=n; i++){
cin >> wej[i];
while(st.size() && st.top().first<=wej[i])st.pop();
if (st.size())ev.push_back({st.top().second,i,st.top().first+wej[i],i,0});
st.push({wej[i],i});
}
for (ll i = 1,a,b,c; i<=m; i++){
cin >> a >> b >> c;
ev.push_back({a,b,c,i,1});
}
sort(ev.begin(),ev.end(),[](query a, query b){return a.x==b.x?a.type<b.type:a.x>b.x;});
for (ll i = 0; i<ev.size(); i++){
if (ev[i].type)odpow[ev[i].ind]=check(ev[i].y)<=ev[i].k;
else update(ev[i].y,ev[i].k);
}
for (ll i = 1; i<=m; i++)cout << odpow[i] << '\n';
}
Compilation message (stderr)
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:56:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for (ll i = 0; i<ev.size(); i++){
| ~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |