Submission #599070

#	Time	Username	Problem	Language	Result	Execution time	Memory
599070		hibiki	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++11	100 / 100	1748 ms	88756 KiB

sortbooks

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define f first
#define s second

int n,m;
int a[1000005], ans[1000005];
stack<int> s;
vector<pair<pair<int, int>, pair<int,int> > > que;

struct node
{
    int mx = 0;
    node *l, *r;
} *root;

node* build(int l, int r)
{
    node *ptr = new node();
    if(l == r) return ptr;
    int mid = (l + r) >> 1;
    ptr->l = build(l, mid);
    ptr->r = build(mid + 1, r);
    return ptr;
}

node* build()
{
    return build(0, n - 1);
}

void update(node *ptr, int l, int r, int po, int val)
{
    ptr->mx = max(ptr->mx, val);
    if(l == r) return ;
    int mid = (l + r) >> 1;
    if(po <= mid) update(ptr->l, l, mid, po, val);
    else update(ptr->r, mid + 1, r, po, val);
}

void update(int po, int val)
{
    update(root, 0, n - 1, po, val);
}

int query(node *ptr, int l, int r, int ll, int rr)
{
    if(ll <= l && r <= rr) return ptr->mx;
    if(rr < l || r < ll) return 0;
    int mid = (l + r) >> 1;
    return max(query(ptr->l, l, mid, ll, rr), query(ptr->r, mid + 1, r, ll, rr));
}

int query(int ll, int rr)
{
    return query(root, 0, n - 1, ll, rr);
}

int main()
{
    scanf("%d %d",&n,&m);
    root = build();
    for(int i = 0; i < n; i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i = 0; i < m ; i++)
    {
        int a, b, c;
        scanf("%d %d %d",&a,&b,&c);
        que.pb({{b - 1, a - 1}, {c, i}});
    }
    sort(que.begin(), que.end());
    int cur = 0;
    for(int i = 0; i < n; i++)
    {
        while(!s.empty() && a[s.top()] <= a[i])
            s.pop();
        if(!s.empty())
            update(s.top(), a[s.top()] + a[i]);
        s.push(i);
        while(cur < m && que[cur].f.f == i)
        {
            ans[que[cur].s.s] = (query(que[cur].f.s, que[cur].f.f) <= que[cur].s.f)? 1:0;
            cur++;
        }
    }
    for(int i = 0; i < m; i++)
        printf("%d\n", ans[i]);
    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
sortbooks.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~
sortbooks.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         scanf("%d %d %d",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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