Submission #174630

#	Time	Username	Problem	Language	Result	Execution time	Memory
174630		_Enkognit	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	1545 ms	262148 KiB

sortbooks

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define ll long long
#define mp make_pair
#define pb push_back
#define ld long double
#define fi first
#define se second
#define pld pair<ld,ld>
#define pll pair<ll,ll>
#define sqr(a) ((a)*(a))
#define pii pair<int,int>
#define y1 Enkognit
#define sqr(a) ((a)*(a))

using namespace std;

mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());

const ll md1=1e9+7, md2=998244357, md3=rnd()%(ll)(1e8), p1=31, p2=37, p3=41;

//template <typename T>
//using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

ll n, m, k, l, r, i, j, b[1000001];
pll a[1000001];

struct node
{
    node *l, *r;
    ll mx;
    node():l(nullptr),r(nullptr),mx(0) {};
};

struct bin_persistent_tree
{
    vector<pair<node*, int> > root;

    void build_new_tree(int n)
    {
        root.pb(mp(new node(),-1e18));
        build(root.back().fi,1,n);
    }

    void build(node *h,int l,int r)
    {
        if (l==r) return;
        int w=(l+r)/2;
        h->l=new node();
        h->r=new node();
        build(h->l,l,w);
        build(h->r,w+1,r);
    }

    void upd(node* h,int l,int r,int x,int k)
    {
        if (l==r) {h->mx=k;return;}
        int w=(l+r)/2;
        if (x<=w) upd(h->l,l,w,x,k); else upd(h->r,w+1,r,x,k);
        h->mx=max(h->l->mx,h->r->mx);
    }

    node* update(node *h,int l,int r,int x,int k)
    {
        if (l==r)
        {
            node* u=new node();
            u->mx=k;
            return u;
        }
        int w=(l+r)/2;
        node *u=new node();
        if (x<=w)
        {
            u->r=h->r;
            u->l=update(h->l,l,w,x,k);
        }else
        {
            u->l=h->l;
            u->r=update(h->r,w+1,r,x,k);
        }
        u->mx=max(u->l->mx,u->r->mx);
        return u;
    }

    int gt(node *h,int l,int r,int x,int y)
    {
        if (x>y) return 0;
        if (l==x && y==r) return h->mx;
        int w=(l+r)/2;
        return max(gt(h->l,l,w,x,min(y,w)), gt(h->l,w+1,r,max(x,w+1),y));
    }
};

bin_persistent_tree g;

pll d[5000001];

void build(int h,int l,int r)
{
    if (l==r) {d[h]=mp(b[l],0);return;}
    int w=(l+r)/2;
    build(h*2,l,w);
    build(h*2+1,w+1,r);
    d[h].fi=max(d[h*2].fi,d[h*2+1].fi);
    ll p=max(d[h*2].se,d[h*2+1].se);
    if (d[h*2].fi>d[h*2+1].fi) d[h].se=max(p,d[h*2].fi+d[h*2+1].fi); else
    {
        ll lr=0, rr=g.root.size()-1;
        while (lr<rr)
        {
            int wr=(lr+rr+1)/2;
            if (g.root[wr].se<d[h*2].fi) lr=wr; else rr=wr-1;
        }
        d[h].se=max(p, (ll)g.gt(g.root[lr].fi,1,n,w+1,r));
    }
}

pll get(int h,int l,int r,int x,int y)
{
    if (x>y) return mp(0,-1);
    if (l==x && y==r) return d[h];
    int w=(l+r)/2;
    pll o1=get(h*2,l,w,x,min(y,w));
    pll o2=get(h*2+1,w+1,r,max(x,w+1),y);
    pll o3=mp(max(o1.fi,o2.fi), max(o1.se,o2.se));
    if (!(x<=w && y>=w+1)) return o3;
    if (o1.fi>o2.fi) o3.se=max(o3.se, o1.fi+o2.fi);else
    {
        ll lr=0, rr=g.root.size()-1;
        while (lr<rr)
        {
            int wr=(lr+rr+1)/2;
            if (g.root[w].se<o2.fi) lr=wr; else rr=wr-1;
            }
        o3.se=max(o3.se, (ll)g.gt(g.root[lr].fi,1,n,w+1,y));
    }
    return o3;
}

int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {cin >> b[i];a[i].fi=b[i];a[i].se=i;}
    sort(a+1,a+n+1);
    g.build_new_tree(n);
    for (int i = 1; i <= n; i++)
    {
        if (a[i].fi==a[i-1].fi) g.upd(g.root.back().fi,1,n,a[i].se,a[i].fi); else
            g.root.pb(mp(g.update(g.root.back().fi,1,n,a[i].se,a[i].fi), a[i].fi));
    }
    //cout << g.gt(g.root[2].fi,1,n,1,n);
    build(1,1,n);
    while (m--)
    {
        int l, r, k;
        cin >> l >> r >> k;
        cout << (bool)(k>=get(1,1,n,l,r).se) << "\n";
    }
}
/*
5 2
3 5 1 8 2
1 3 6
2 5 9
*/

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