oj.uz

Submission #541048

# Submission time Handle Problem Language Result Execution time Memory
541048 2022-03-22T07:22:38 Z balbit Dungeon 3 (JOI21_ho_t5) C++14
100 / 100
 3850 ms 431488 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 22044 KB Output is correct
2 Correct 38 ms 22140 KB Output is correct
3 Correct 34 ms 21556 KB Output is correct
4 Correct 40 ms 22032 KB Output is correct
5 Correct 36 ms 22324 KB Output is correct
6 Correct 35 ms 21608 KB Output is correct
7 Correct 44 ms 22036 KB Output is correct
8 Correct 39 ms 22096 KB Output is correct
9 Correct 32 ms 21676 KB Output is correct
10 Correct 41 ms 22068 KB Output is correct
11 Correct 37 ms 22096 KB Output is correct
12 Correct 34 ms 21460 KB Output is correct
13 Correct 41 ms 21964 KB Output is correct
14 Correct 38 ms 22144 KB Output is correct
15 Correct 36 ms 22264 KB Output is correct
16 Correct 39 ms 22124 KB Output is correct
17 Correct 42 ms 21868 KB Output is correct
18 Correct 36 ms 21900 KB Output is correct
19 Correct 36 ms 21132 KB Output is correct
20 Correct 32 ms 23612 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 70788 KB Output is correct
2 Correct 636 ms 68324 KB Output is correct
3 Correct 597 ms 69420 KB Output is correct
4 Correct 547 ms 60584 KB Output is correct
5 Correct 722 ms 69600 KB Output is correct
6 Correct 2702 ms 241968 KB Output is correct
7 Correct 2969 ms 217000 KB Output is correct
8 Correct 2949 ms 240688 KB Output is correct
9 Correct 2699 ms 187276 KB Output is correct
10 Correct 2922 ms 223084 KB Output is correct
11 Correct 2854 ms 221396 KB Output is correct
12 Correct 2724 ms 185160 KB Output is correct
13 Correct 3650 ms 216608 KB Output is correct
14 Correct 3603 ms 220856 KB Output is correct
15 Correct 1965 ms 431488 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3522 ms 196044 KB Output is correct
2 Correct 2703 ms 191880 KB Output is correct
3 Correct 2458 ms 151600 KB Output is correct
4 Correct 3011 ms 188660 KB Output is correct
5 Correct 2225 ms 186172 KB Output is correct
6 Correct 2625 ms 187372 KB Output is correct
7 Correct 3032 ms 188736 KB Output is correct
8 Correct 2337 ms 180388 KB Output is correct
9 Correct 2170 ms 142520 KB Output is correct
10 Correct 2088 ms 408292 KB Output is correct
11 Correct 2300 ms 186172 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 22044 KB Output is correct
2 Correct 38 ms 22140 KB Output is correct
3 Correct 34 ms 21556 KB Output is correct
4 Correct 40 ms 22032 KB Output is correct
5 Correct 36 ms 22324 KB Output is correct
6 Correct 35 ms 21608 KB Output is correct
7 Correct 44 ms 22036 KB Output is correct
8 Correct 39 ms 22096 KB Output is correct
9 Correct 32 ms 21676 KB Output is correct
10 Correct 41 ms 22068 KB Output is correct
11 Correct 37 ms 22096 KB Output is correct
12 Correct 34 ms 21460 KB Output is correct
13 Correct 41 ms 21964 KB Output is correct
14 Correct 38 ms 22144 KB Output is correct
15 Correct 36 ms 22264 KB Output is correct
16 Correct 39 ms 22124 KB Output is correct
17 Correct 42 ms 21868 KB Output is correct
18 Correct 36 ms 21900 KB Output is correct
19 Correct 36 ms 21132 KB Output is correct
20 Correct 32 ms 23612 KB Output is correct
21 Correct 538 ms 70788 KB Output is correct
22 Correct 636 ms 68324 KB Output is correct
23 Correct 597 ms 69420 KB Output is correct
24 Correct 547 ms 60584 KB Output is correct
25 Correct 722 ms 69600 KB Output is correct
26 Correct 2702 ms 241968 KB Output is correct
27 Correct 2969 ms 217000 KB Output is correct
28 Correct 2949 ms 240688 KB Output is correct
29 Correct 2699 ms 187276 KB Output is correct
30 Correct 2922 ms 223084 KB Output is correct
31 Correct 2854 ms 221396 KB Output is correct
32 Correct 2724 ms 185160 KB Output is correct
33 Correct 3650 ms 216608 KB Output is correct
34 Correct 3603 ms 220856 KB Output is correct
35 Correct 1965 ms 431488 KB Output is correct
36 Correct 3522 ms 196044 KB Output is correct
37 Correct 2703 ms 191880 KB Output is correct
38 Correct 2458 ms 151600 KB Output is correct
39 Correct 3011 ms 188660 KB Output is correct
40 Correct 2225 ms 186172 KB Output is correct
41 Correct 2625 ms 187372 KB Output is correct
42 Correct 3032 ms 188736 KB Output is correct
43 Correct 2337 ms 180388 KB Output is correct
44 Correct 2170 ms 142520 KB Output is correct
45 Correct 2088 ms 408292 KB Output is correct
46 Correct 2300 ms 186172 KB Output is correct
47 Correct 3850 ms 211348 KB Output is correct
48 Correct 3089 ms 220760 KB Output is correct
49 Correct 2930 ms 181068 KB Output is correct
50 Correct 3487 ms 208756 KB Output is correct
51 Correct 2933 ms 227696 KB Output is correct
52 Correct 2937 ms 224764 KB Output is correct
53 Correct 3498 ms 188052 KB Output is correct
54 Correct 2758 ms 187476 KB Output is correct
55 Correct 2561 ms 146900 KB Output is correct
56 Correct 2270 ms 389584 KB Output is correct
57 Correct 2637 ms 193756 KB Output is correct