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;
int pogolem[1000000];
int niza[1000000];
int drvo[2500000];
int p;
int update(int l,int r,int poz,int k)
{
if (p<l || r<p) return drvo[poz];
if (l==r)
{
drvo[poz] = max(drvo[poz],k);
return drvo[poz];
}
int mid = (l+r)/2;
drvo[poz] = max(update(l,mid,poz*2,k),update(mid+1,r,poz*2+1,k));
return drvo[poz];
}
int najdi(int l,int r,int poz,int levo,int desno)
{
if (levo<=l && r<=desno) return drvo[poz];
if (r<levo || desno<l) return 0;
int mid = (l+r)/2;
return max(najdi(l,mid,poz*2,levo,desno),najdi(mid+1,r,poz*2+1,levo,desno));
}
int main()
{
int n,q;
cin>>n>>q;
int ns = 1;
while (ns<n) ns*=2;
stack<int> s;
for (int i=1;i<=n;i++)
{
int a;
cin>>a;
niza[i] = a;
while(s.size() && niza[s.top()]<=a) s.pop();
if (s.size()) pogolem[i] = s.top();
else pogolem[i] = -1;
s.push(i);
}
vector<tuple<int,int,int,int> > pras;
for (int i=0;i<q;i++)
{
int a,b,c;
cin>>a>>b>>c;
pras.push_back({b,a,c,i});
}
sort(pras.begin(),pras.end());
int t = 0;
vector<pair<int,int> > odg;
for (int i=1;i<=n;i++)
{
if (pogolem[i]!=-1)
{
p = pogolem[i];
update(1,ns,1,niza[i]+niza[p]);
}
while(t<pras.size() && get<0>(pras[t])==i)
{
int x = najdi(1,ns,1, get<1>(pras[t]),get<0>(pras[t]));
if (x<=get<2>(pras[t])) odg.push_back({get<3>(pras[t]),1});
else odg.push_back({get<3>(pras[t]),0});
t++;
}
}
sort(odg.begin(),odg.end());
for (auto a : odg)
cout<<a.second<<endl;
return 0;
}
Compilation message (stderr)
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:70:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | while(t<pras.size() && get<0>(pras[t])==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... |