| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 153686 | semiauto | Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
solve(i+1+N-1,par[i]-1+N-1,1,N,2*N-1);#include <bits/stdc++.h>
using namespace std;
int n,m,i,j,l,r,ans,N=1024*1024;
int mas[1000001],val[1000001],tree[2048*1024];
pair <int,int> p[1000001][20];
vector <int> v[1000001];
void dfs(int u) {
int i;
for (i=1;i<20;i++)
if (p[p[u][i-1].first][i-1].first)
p[u][i]={p[p[u][i-1].first][i-1].first,max(p[u][i-1].second,p[p[u][i-1].first][i-1].second)};
for (i=0;i<(v[u].size());i++)
dfs(v[u][i]);
}
int solve(int x,int y,int p,int l,int r) {
if (l>y || x>r)
return 0;
if (l>=x && r<=y)
return tree[p];
return max(solve(x,y,2*p,l,(l+r)/2),solve(x,y,2*p+1,(l+r)/2+1,r));
}
void build_tree(int p) {
if (p>=N) {
if ((p-N+1)<=n)
tree[p]=mas[p-N+1];
return;
}
build_tree(2*p);
build_tree(2*p+1);
tree[p]=max(tree[2*p],tree[2*p+1]);
}
int main() {
cin>>n>>m;
for (i=1;i<=n;i++)
scanf("%d",&(mas[i]));
build_tree(1);
for (i=n;i>0;i--) {
for (;r>0;r--)
if (mas[val[r]]>=mas[i])
break;
p[i][0].first=val[r];
if (val[r]>(i+1))
p[i][0].second=mas[i]+solve(i+1+N-1,val[r]-1+N-1,1,N,2*N-1);
v[val[r]].push_back(i);
val[++r]=i;
}
for (i=0;i<(v[0].size());i++)
dfs(v[0][i]);
for (mas[0]=1;mas[0]<=m;mas[0]++) {
scanf("%d %d %d",&l,&r,&j);
if (l==r) {
printf("1\n");
continue;
}
ans=0;
for (i=19;i>=0;i--)
if (p[l][i].first && p[l][i].first<=r) {
ans=max(ans,p[l][i].second);
l=p[l][i].first;
}
if (r>l)
ans=max(ans,mas[l]+solve(l+1+N-1,r+N-1,1,N,2*N-1));
if (ans>j)
printf("0\n");
else
printf("1\n");
}
}