# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
371224 | daniel920712 | Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) | C++14 | 2063 ms | 121892 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.
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <utility>
#include <vector>
#include <algorithm>
#include <deque>
using namespace std;
struct A
{
int l,r;
int nxl,nxr;
int big;
}Node[2000005];
vector < pair < pair < int , int > , int > > where[2000005];
deque < int > how;
int all[2000005];
int last[2000005];
int ans[2000005];
int now=1;
void build(int l,int r,int here)
{
int i;
Node[here].l=l;
Node[here].r=r;
if(l==r)
{
Node[here].big=0;
return;
}
Node[here].nxl=now++;
Node[here].nxr=now++;
build(l,(l+r)/2,Node[here].nxl);
build((l+r)/2+1,r,Node[here].nxr);
Node[here].big=0;
}
int Find(int l,int r,int here)
{
pair < int , int > t,a,b;
int c;
if(Node[here].l==l&&Node[here].r==r) return Node[here].big;
if(r<=(Node[here].l+Node[here].r)/2) return Find(l,r,Node[here].nxl);
else if(l>(Node[here].l+Node[here].r)/2) return Find(l,r,Node[here].nxr);
else return max(Find(l,(Node[here].l+Node[here].r)/2,Node[here].nxl),Find((Node[here].l+Node[here].r)/2+1,Node[here].r,Node[here].nxr));
}
void cha(int where,int con,int here)
{
pair < int , int > t,a,b;
int c;
if(Node[here].l==where&&Node[here].r==where)
{
Node[here].big=con;
return;
}
if(where<=(Node[here].l+Node[here].r)/2) cha(where,con,Node[here].nxl);
else cha(where,con,Node[here].nxr);
Node[here].big=max(Node[Node[here].nxl].big,Node[Node[here].nxr].big);
}
int main()
{
int N,M,x,y,z,t,i,j,big;
scanf("%d %d",&N,&M);
build(0,N,0);
for(i=1;i<=N;i++) scanf("%d",&all[i]);
for(i=0;i<M;i++)
{
scanf("%d %d %d",&x,&y,&z);
where[y].push_back(make_pair(make_pair(x,z),i));
}
for(i=1;i<=N;i++)
{
while(!how.empty()&&all[i]>=all[how.back()]) how.pop_back();
if(!how.empty()) cha(how.back(),all[how.back()]+all[i],0);
how.push_back(i);
for(auto j:where[i]) ans[j.second]=Find(j.first.first,i,0)<=j.first.second;
}
for(i=0;i<M;i++)
{
printf("%d\n",ans[i]);
}
return 0;
}
Compilation message (stderr)
# | 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... |