Submission #675881

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
675881	2022-12-28T09:30:35 Z	alexdd	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	13 / 100	1182 ms	99356 KB

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;
        for(int j=q[i].le;j<=q[i].ri;j++)
        {
            if(w[j]>x)
            {
                mij=j;
                break;
            }
        }
        /*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;
}
/**

*/

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:114:13: warning: unused variable 'st' [-Wunused-variable]
  114 |         int st,dr,mij;
      |             ^~
sortbooks.cpp:114:16: warning: unused variable 'dr' [-Wunused-variable]
  114 |         int st,dr,mij;
      |                ^~
sortbooks.cpp:84:14: warning: 'mij' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |     if(aju[st]==aju[dr])
      |        ~~~~~~^
sortbooks.cpp:114:19: note: 'mij' was declared here
  114 |         int st,dr,mij;
      |                   ^~~

Subtask #1
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Incorrect	1 ms	340 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Incorrect	1 ms	340 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1182 ms	89864 KB	Output is correct
2	Correct	1141 ms	99356 KB	Output is correct
3	Correct	1073 ms	92892 KB	Output is correct
4	Correct	1083 ms	92884 KB	Output is correct
5	Correct	1077 ms	92940 KB	Output is correct