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;
struct RMQ_MAX
{
vector<vector<int>>ret;
vector<int>mylog;
void build(int n,int a[])
{
ret.resize(n+1);
mylog.resize(n+1);
for(int i=2;i<=n;i++)
{
mylog[i]=1+mylog[i/2];
}
for(int i=1;i<=n;i++)
{
ret[i].resize(mylog[n]+1,-(1<<30));
ret[i][0]=a[i];
}
for(int k=1;(1<<k)<=n;k++)
{
for(int i=1;i+(1<<k)-1<=n;i++)
{
ret[i][k]=max(ret[i][k-1],ret[i+(1<<(k-1))][k-1]);
}
}
}
int gt(int l,int r)
{
int k=mylog[r-l+1];
return max(ret[l][k],ret[r-(1<<k)+1][k]);
}
};
RMQ_MAX rm;
typedef long long ll;
const int N=(int)1e5+7;
int n,m;
int a[N];
int b[N];
ll ps[N];
ll gt(int l,int r)
{
return ps[r]-ps[l-1];
}
struct info
{
int a;
int b;
};
bool cmp(info x,info y)
{
return x.b<y.b;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i]>>b[i];
ps[i]=ps[i-1]+a[i];
}
rm.build(n,b);
while(m--)
{
int l,r;
cin>>l>>r;
ll tots=gt(l,r);
int big=rm.gt(l,r);
/// cout<<":"<<tots<<" , "<<big<<"\n";
if(tots>=(ll)big)
{
cout<<"0\n";
continue;
}
vector<info>keks;
for(int i=l;i<=r;i++)
{
keks.push_back({a[i],b[i]});
}
sort(keks.begin(),keks.end(),cmp);
int tos=0;
bool ok=1;
for(auto &it:keks)
{
tos+=it.a;
if(tos>=it.b)
{
ok=0;
break;
}
}
cout<<(int)ok<<"\n";
/// cout<<"?\n";
}
}
/**
4 3
1 10
14 18
2 7
10 12
3 4
2 4
1 3
**/
# | 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... |