Submission #371178

#	Time	Username	Problem	Language	Result	Execution time	Memory
371178		daniel920712	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	77 / 100	1523 ms	123028 KiB

sortbooks

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <utility>
#include <vector>
#include <algorithm>

using namespace std;
struct A
{
    int l,r;
    int nxl,nxr;
    pair < int , int > ans;
    vector < int > all;
}Node[2000005];
int all[2000005];
int last[2000005];
int now=1;
pair < int , int > operator +(pair < int , int > a,pair < int , int > b)
{
    pair < int , int > ans;
    ans.first=max(a.first,b.first);
    ans.second=max(a.second,b.second);
    return ans;
}
void build(int l,int r,int here)
{
    int i;
    Node[here].l=l;
    Node[here].r=r;
    for(i=l;i<=r;i++) Node[here].all.push_back(all[i]);
    sort(Node[here].all.begin(),Node[here].all.end());
    if(l==r)
    {
        Node[here].ans=make_pair(all[l],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].ans=Node[Node[here].nxl].ans+Node[Node[here].nxr].ans;
}

int Find2(int l,int r,int con,int here)
{
    int a,b;
    if(l==Node[here].l&&r==Node[here].r)
    {
        if(lower_bound(Node[here].all.begin(),Node[here].all.end(),con)==Node[here].all.begin()) return -1;
        return *prev(lower_bound(Node[here].all.begin(),Node[here].all.end(),con));
    }
    if(r<=(Node[here].l+Node[here].r)/2) return Find2(l,r,con,Node[here].nxl);
    else if(l>(Node[here].l+Node[here].r)/2) return Find2(l,r,con,Node[here].nxr);
    else
    {
        a=Find2(l,(Node[here].l+Node[here].r)/2,con,Node[here].nxl);
        b=Find2((Node[here].l+Node[here].r)/2+1,r,con,Node[here].nxr);
        return max(a,b);
    }

}

void build2(int here)
{
    if(Node[here].l==Node[here].r) return;
    build2(Node[here].nxl);
    build2(Node[here].nxr);
    pair < int , int > t,a,b;
    int c;
    a=Node[Node[here].nxl].ans;
    b=Node[Node[here].nxr].ans;
    c=Find2((Node[here].l+Node[here].r)/2+1,Node[here].r,a.first,0);
    t=a+b;
    if(a.first>c&&c!=-1) t.second=max(t.second,a.first+c);
    Node[here].ans=t;
}
pair < int , 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].ans;
    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
    {
        a=Find(l,(Node[here].l+Node[here].r)/2,Node[here].nxl);
        b=Find((Node[here].l+Node[here].r)/2+1,r,Node[here].nxr);
        t=a+b;
        c=Find2((Node[here].l+Node[here].r)/2+1,r,a.first,0);
        if(a.first>c&&c!=-1) t.second=max(t.second,a.first+c);

        return t;
    }
}
int main()
{
    int N,M,x,y,z,t,i,j,big;
    scanf("%d %d",&N,&M);

    for(i=1;i<=N;i++) scanf("%d",&all[i]);
    if(N<=200000&&M<=200000)
    {
        build(1,N,0);
        build2(0);
        while(M--)
        {
            scanf("%d %d %d",&x,&y,&z);
            if(Find(x,y,0).second<=z) printf("1\n");
            else printf("0\n");
        }
    }
    else
    {
        last[1]=1;
        for(i=2;i<=N;i++)
        {
            if(all[i]>=all[i-1]) last[i]=last[i-1];
            else last[i]=i;
        }
        while(M--)
        {
            scanf("%d %d %d",&x,&y,&z);
            if(last[y]<=x) printf("1\n");
            else printf("0\n");
        }
    }


   return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:98:19: warning: unused variable 't' [-Wunused-variable]
   98 |     int N,M,x,y,z,t,i,j,big;
      |                   ^
sortbooks.cpp:98:23: warning: unused variable 'j' [-Wunused-variable]
   98 |     int N,M,x,y,z,t,i,j,big;
      |                       ^
sortbooks.cpp:98:25: warning: unused variable 'big' [-Wunused-variable]
   98 |     int N,M,x,y,z,t,i,j,big;
      |                         ^~~
sortbooks.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   99 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
sortbooks.cpp:101:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |     for(i=1;i<=N;i++) scanf("%d",&all[i]);
      |                       ~~~~~^~~~~~~~~~~~~~
sortbooks.cpp:108:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  108 |             scanf("%d %d %d",&x,&y,&z);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:123:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  123 |             scanf("%d %d %d",&x,&y,&z);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~

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