Submission #675877

#	Time	Username	Problem	Language	Result	Execution time	Memory
675877		alexdd	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	3076 ms	82132 KiB

sortbooks

#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = LLONG_MAX;
struct intrebare
{
    int le,ri,k;
    int index;
};
bool cmp(intrebare x, intrebare y)
{
    return x.le < y.le;
}
int n,m;
int w[1000001];
intrebare q[1000001];
int rez[1000001];
pair<int,int> combine(pair<int,int> x, pair<int,int> y)
{
    pair<int,int> aux;
    aux.first = min(x.first,y.first);
    aux.second = max(x.second,y.second);
    return aux;
}
pair<int,int> aint[4100000];///aint.first -> minim
                            ///aint.second -> maxim
void build(int nod, int st, int dr)
{
    if(st==dr)
    {
        aint[nod]={w[st],w[st]};
        return;
    }
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
    aint[nod]=combine(aint[nod*2],aint[nod*2+1]);
}
void upd(int nod, int st, int dr, int poz, int newval)
{
    if(st==dr)
    {
        aint[nod]={newval,newval};
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij)
        upd(nod*2,st,mij,poz,newval);
    else
        upd(nod*2+1,mij+1,dr,poz,newval);
    aint[nod]=combine(aint[nod*2],aint[nod*2+1]);
}
pair<int,int> qry(int nod, int st, int dr, int le, int ri)
{
    if(le>ri)
        return {INF,0};
    if(le==st && dr==ri)
        return aint[nod];
    int mij=(st+dr)/2;
    return combine(qry(nod*2,st,mij,le,min(mij,ri)),
                   qry(nod*2+1,mij+1,dr,max(mij+1,le),ri));
}
int aju[1000001];
void precalc()
{
    int cur=0;
    aju[1]=0;
    for(int i=2;i<=n;i++)
    {
        if(w[i]>=w[i-1])
        {
            aju[i]=cur;
        }
        else
        {
            cur++;
            aju[i]=cur;
        }
    }
}
bool isCresc(int st, int dr)
{
    if(aju[st]==aju[dr])
        return 1;
    return 0;
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>w[i];
    precalc();
    build(1,1,n);
    for(int i=0;i<m;i++)
    {
        cin>>q[i].le>>q[i].ri>>q[i].k;
        q[i].index=i;
    }
    //sort(q,q+m,cmp);
    int x;
    pair<int,int> cop;
    for(int i=0;i<m;i++)
    {
        cop = qry(1,1,n,q[i].le,q[i].ri);
        x = q[i].k - cop.first;
        if(cop.second <= x)
        {
            rez[q[i].index]=1;
            continue;
        }
        int st,dr,mij;
        st=q[i].le;
        dr=q[i].ri;
        mij=q[i].le;
        while(st<=dr)
        {
            mij=(st+dr)/2;
            if(qry(1,1,n,q[i].le,mij).second > x)
            {
                if(mij==q[i].le || qry(1,1,n,q[i].le,mij-1).second <= x)
                    break;
                else
                    dr=mij-1;
            }
            else
                st=mij+1;
        }
        if(isCresc(mij,q[i].ri))
            rez[q[i].index]=1;
        else
            rez[q[i].index]=0;
    }
    for(int i=0;i<m;i++)
        cout<<rez[i]<<"\n";
    return 0;
}
/**

*/

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23