Submission #541048

#	Time	Username	Problem	Language	Result	Execution time	Memory
541048		balbit	Dungeon 3 (JOI21_ho_t5)	C++14	100 / 100	3850 ms	431488 KiB

Main

#include <bits/stdc++.h>
#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

#ifdef BALBIT
const int maxn = 2e4+5;
#else
const int maxn = 2e5+5;

#endif
int n,numq;

ll ans[maxn];
ll A[maxn], B[maxn];

struct TRI{
    int t, h, u, val;
};
vector<TRI > tri; // triangle with {time T, {height (A), x pos (U of intersection)} }

struct QUE{
    int t, h, u, id, dir;
};

ll s[maxn], si[maxn];

void MO(int e, int v, int vi) {
    for (++e; e<maxn; e+=e&-e) {
        s[e] += v; si[e] += vi;
    }
}

ll QU(int e, ll i) {
    ll re = 0;
    for (++e; e>0; e-=e&-e) {
        re += s[e] + si[e] * (i);
    }
    return re;
}

vector<ll> allh; // for sorting

struct HA{
    vector<TRI> v[maxn];
    vector<QUE> q[maxn];

    void setup(){
        allh.clear();
        REP(i,maxn) for (auto &e : v[i]) {
            allh.pb(e.h);
        }
        SORT_UNIQUE(allh);
    }

    inline int geth(ll x) {
        return lower_bound(ALL(allh), x+1) - allh.begin() - 1;
    }

    void cdq(int L, int R) {
        if (L > R) {
            return;
        }
        int mid = (L+R)/2;
        vector<TRI> tt;
        vector<QUE> qq;
        for (int i = L; i<=mid; ++i) {
            qq.insert(qq.end(), ALL(q[i]));
        }
        for (int i = mid; i<=R; ++i) {
            tt.insert(tt.end(), ALL(v[i]));
        }

        sort(ALL(tt), [&](TRI a, TRI b){return a.u < b.u;});
        sort(ALL(qq), [&](QUE a, QUE b){return a.u < b.u;});
        int at = 0;

        for (QUE e : qq) {
            while (at != SZ(tt) && tt[at].u <= e.u) {
                MO(geth(tt[at].h), -(tt[at].val) * (tt[at].h-1), tt[at].val);
                ++at;
            }
            bug(e.dir, e.h,  QU(geth(e.h), e.h));
            ans[e.id] += e.dir * QU(geth(e.h), e.h);
        }

        REP(j, at) {
            MO(geth(tt[j].h), - (-(tt[j].val) * (tt[j].h-1)), - tt[j].val);
        }

        cdq(L, mid-1); cdq(mid+1, R);
    }
};

int seg[2 * maxn];

void modify(int p, int value) {
    for (seg[p += maxn] = value; p > 1; p >>= 1) seg[p>>1] = max(seg[p] , seg[p^1]);
}

int query(int l, int r) {
    int res = 0;
    for (l += maxn, r += maxn; l < r; l >>= 1, r >>= 1) {
        if (l&1) res = max(res, seg[l++]);
        if (r&1) res = max(res, seg[--r]);
    }
    return res;
}


signed main(){
    IOS();
    cin>>n>>numq;
    REP1(i,n) {
        cin>>A[i];
        modify(i-1, A[i]);
        if (i) A[i] += A[i-1];
    }
    ++n;
    REP(i,n) {
        A[i] = A[n-1] - A[i];
        bug(i, A[i]);
    }
    vector<int> stk;

    REP(i,n-1) {
        cin>>B[i];
    }

    for (int i = n-1; i>=0; --i) {
        tri.pb({i, A[i], 0, B[i]});
        ll subbed = 0;
        while (!stk.empty() && B[stk.back()] > B[i]) {
            int j = stk.back();
            tri.pb({i, A[j], A[i] - A[j], -(B[j] - subbed)});
            subbed = B[j];
            stk.pop_back();
        }
        if (!stk.empty()) {
            int j = stk.back();
            tri.pb({i, A[j], A[i] - A[j], -B[i] + subbed});
        }
        stk.pb(i);
    }

    HA slant, stra;

    for (TRI t : tri) {
        bug(t.t, t.h, t.u, t.val);
        t.h += t.u;
        slant.v[t.t].pb(t);
        t.h -= t.u;
        t.h += 1;
        stra.v[t.t].pb(t);
    }

    REP(i, numq) {
        int S,T,U; cin>>S>>T>>U;


        --S; --T;
        if (query(S,T) > U) {
            ans[i] = -1; continue;
        }
        --U;
        bug(A[S]+U, A[T]+U);
        slant.q[S].pb({S, A[S]+U, U, i, 1});
        slant.q[S].pb({S, A[T]+U, U, i, -1});

        stra.q[S].pb({S, A[S], U, i, -1});
        stra.q[S ].pb({S, A[T], U, i, 1});
    }

    slant.setup();
    slant.cdq(0, n);


    stra.setup();
    stra.cdq(0, n);

    REP(i,numq) {
        cout<<ans[i]<<endl;
    }
}

/*
1 1
5 100
1 2 5

1 1
1 100
1 1

5 1
3 4 1 1 4
2 5 1 2 1
5 6 3
*/

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 31 / 31
• Subtask 4: 44 / 44