Submission #174681

#	Time	Username	Problem	Language	Result	Execution time	Memory
174681		_Enkognit	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	64 / 100	2456 ms	155664 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], ttt=1;
pll a[1000001];

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

struct bin_persistent_tree
{
    vector<pair<node*, ll> > 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) {h->mx=-1e18;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);
        h->mx=-1e18;
    }

    node* update(node *h,int l,int r,int x,ll 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;
    }

    ll gt(node *h,int l,int r,int x,int y)
    {
        if (x>y) return -1e18;
        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->r,w+1,r,max(x,w+1),y));
    }
};

bin_persistent_tree g;

pll d[5000001];
ll di[5000001];

void build(int h,int l,int r)
{
    if (l==r) {d[h]=mp(b[l],0);di[h]=b[l];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);
    di[h]=min(di[h*2],di[h*2+1]);
    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;
        }
        ll o=g.gt(g.root[lr].fi,1,n,w+1,r);
        //cout << d[h*2].fi << " " << o << " " << w+1 << " " << r << "\n";
        d[h].se=max(p, d[h*2].fi+o);
    }
    //cout << l << " " << r << " : " << d[h].se << "\n";
}

pll get(int h,int l,int r,int x,int y)
{
    if (x>y) return mp(0,-1e18);
    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) || o1.se<0 || o2.se<0) 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[wr].se<o1.fi) lr=wr; else rr=wr-1;
        }
        ll o=g.gt(g.root[lr].fi,1,n,w+1,y);
        o3.se=max(o3.se, o1.fi+o);
        //if (o>=o1.fi) cout << x << "-" << y << " " << o1.fi << " " << g.root[lr].se << "\n";
    }
    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;
    ll p=1e18;
    for (int i = 1; i <= n; i++) {cin >> b[i];a[i].fi=b[i];a[i].se=i;p=min(p,b[i]);}
    vector<pair<pll,ll> > v;
    while (m--)
    {
        ll l, r, k;
        cin >> l >> r >> k;
        if (k>=p) ttt=0;
        v.pb(mp(mp(l,r),k));
    }
    if (ttt)
    {
        vector <ll> p;
        for (int i = 1; i <= n; i++)
            if (b[i]!=b[i+1]) p.pb(i);
        p.pb(n);
        for (int i = 0; i < v.size(); i++)
        {
            ll l=0, r=p.size()-1;
            while (l<r)
            {
                ll w=(l+r+1)/2;
                if (v[i].fi.fi<=p[w]) l=w; else r=w-1;
            }
            cout << (v[i].fi.se<=p[l]) << "\n";
        }
        exit(0);
    }
    sort(a+1,a+n+1);
    g.build_new_tree(n);
    for (int i = 1; i <= n; i++)
    {
        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);
    for (int i = 0; i < v.size(); i++)
    {
        cout << (v[i].se>=get(1,1,n,v[i].fi.fi,v[i].fi.se).se) << "\n";
    }
}
/*
5 2
3 5 1 8 2
1 3 6
2 5 3
*/

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:169:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < v.size(); i++)
                         ~~^~~~~~~~~~
sortbooks.cpp:189:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); i++)
                     ~~^~~~~~~~~~

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