Submission #153578

#	Time	Username	Problem	Language	Result	Execution time	Memory
153578		leatherman	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	34 / 100	3019 ms	110692 KiB

sortbooks

#include <bits/stdc++.h>

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

#define ll int
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sqr(x) (x)*(x)
#define PB push_back

using namespace std;
typedef long double ld;
const ll N = 1123456;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());
//vector<pair<ll, ll> > v;
vector<ll> of[N],q[N],pisos
;
pair<ll, ll> b[N];
ll ans[N],t[4 * N],a[N],l,r,x,k,limit,n,Q;
void upd(ll v,ll tl,ll tr,ll pos,ll val)
{
    if(tl == tr)
    {
        t[v] = max(t[v], val);
        return;
    }
    ll tm = (tl + tr) / 2;
    if(pos <= tm)
        upd(2 * v, tl, tm, pos, val);
    else
        upd(2 * v + 1, tm + 1, tr, pos, val);
    t[v] = max(t[2 * v], t[2 * v + 1]);
}
ll get(ll v,ll tl,ll tr,ll l,ll r)
{
    if(l > r)
        return 0;
    if(tl == l && tr == r)
        return t[v];
    ll tm = (tl + tr) / 2;
    return max(get(2 * v, tl, tm, l, min(r, tm)), get(2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
}
int main()
{
    ios_base::sync_with_stdio();
    cin.tie(0);
    cout.tie(0);
    cin>>n>>Q;
    for(int i = 1; i <= n; i++) cin>>a[i];
    vector<pair<ll, ll> > v1;
    v1.PB({1e9, 0ll});
    for(int i = 1; i <= n; i++)
    {
        ll x  = a[i];
        while(x >= v1.back().fi) v1.pop_back();
        of[v1.back().se].PB(i);
//        cout<<i<<" - "<<v1.back().se<<endl;
        v1.PB({x, i});
    }
    for(int i = 1; i <= Q; i++)
    {
        cin>>l>>r>>k;
        b[i] = {r, k};
        q[l].PB(i);
        pisos.PB(l);
    }
    limit = n;
    sort(all(pisos));
    pisos.erase(unique(all(pisos)), pisos.end());
    reverse(all(pisos));
    for(auto l : pisos)
    {
        while(limit >= l)
        {
            for(auto j : of[limit]) upd(1, 1, n, j, a[j] + a[limit]);
            of[limit].clear();
            limit--;
        }
        for(auto i : q[l])
        {
            r = b[i].fi;
            x = get(1, 1, n, l, r);
//        cout<<l<<" "<<r<<" = "<<x<<endl;
            ans[i] = (x <= b[i].se);
        }
    }
    for(int i = 1; i <= Q; i++)
        cout<<ans[i]<<endl;
    return 0;
}

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