Submission #371224

#	Time	Username	Problem	Language	Result	Execution time	Memory
371224		daniel920712	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	2063 ms	121892 KiB

sortbooks

#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)

sortbooks.cpp: In function 'void build(int, int, int)':
sortbooks.cpp:25:9: warning: unused variable 'i' [-Wunused-variable]
   25 |     int i;
      |         ^
sortbooks.cpp: In function 'int Find(int, int, int)':
sortbooks.cpp:45:9: warning: unused variable 'c' [-Wunused-variable]
   45 |     int c;
      |         ^
sortbooks.cpp: In function 'void cha(int, int, int)':
sortbooks.cpp:54:9: warning: unused variable 'c' [-Wunused-variable]
   54 |     int c;
      |         ^
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:68:19: warning: unused variable 't' [-Wunused-variable]
   68 |     int N,M,x,y,z,t,i,j,big;
      |                   ^
sortbooks.cpp:68:23: warning: unused variable 'j' [-Wunused-variable]
   68 |     int N,M,x,y,z,t,i,j,big;
      |                       ^
sortbooks.cpp:68:25: warning: unused variable 'big' [-Wunused-variable]
   68 |     int N,M,x,y,z,t,i,j,big;
      |                         ^~~
sortbooks.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
sortbooks.cpp:71:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |     for(i=1;i<=N;i++) scanf("%d",&all[i]);
      |                       ~~~~~^~~~~~~~~~~~~~
sortbooks.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |         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: 23 / 23