oj.uz

Submission #534238

# Submission time Handle Problem Language Result Execution time Memory
534238 2022-03-08T02:41:14 Z wiwiho Dungeon 3 (JOI21_ho_t5) C++14
100 / 100
 1105 ms 331344 KB 
#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

ll ifloor(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a < 0) return (a - b + 1) / b;
    else return a / b;
}

ll iceil(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a > 0) return (a + b - 1) / b;
    else return a / b;
}

const int SZ = 20;
struct SparseTable{
    int n;
    vector<vector<ll>> st;
    vector<ll> a;
    int argmin(int x, int y){
        return a[x] <= a[y] ? x : y;
    }
    SparseTable(vector<ll>& a): a(a){
        n = a.size();
        n--;
        st.resize(SZ, vector<ll>(n + 1));
        iota(iter(st[0]), 0);
        for(int i = 1; i < SZ; i++){
            for(int j = 1; j + (1 << i) - 1 <= n; j++){
                st[i][j] = argmin(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
            }
        }
    }
    int query(int l, int r){
        int lg = __lg(r - l + 1);
        return argmin(st[lg][l], st[lg][r - (1 << lg) + 1]);
    }
};
struct SparseTableMax{
    int n;
    vector<vector<ll>> st;
    vector<ll> a;
    int argmin(int x, int y){
        return a[x] >= a[y] ? x : y;
    }
    SparseTableMax(vector<ll>& a): a(a){
        n = a.size();
        n--;
        st.resize(SZ, vector<ll>(n + 1));
        iota(iter(st[0]), 0);
        for(int i = 1; i < SZ; i++){
            for(int j = 1; j + (1 << i) - 1 <= n; j++){
                st[i][j] = argmin(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
            }
        }
    }
    ll query(int l, int r){
        int lg = __lg(r - l + 1);
        return a[argmin(st[lg][l], st[lg][r - (1 << lg) + 1])];
    }
};

struct Info{
    ll v1 = 0, v2 = 0;
};

Info merge(Info a, Info b, int lsz){
    Info c;
    c.v1 = a.v1 + b.v1;
    c.v2 = a.v2 + a.v1 * lsz + b.v2;
    return c;
}

struct Node{
    Info v;
    int l = -1, r = -1;
};

struct SegmentTree{
    
    vector<Node> st;
    int ts = 1;
    SegmentTree(): st(1e7) {}

    Info getv(int id){
        if(id == -1) return Info();
        return st[id].v;
    }

    void pull(int L, int R, int id){
        int M = (L + R) / 2;
        st[id].v = merge(getv(st[id].l), getv(st[id].r), R - M);
    }

    int modify(ll x, ll v, int L = 0, int R = 100000000, int id = 0){
        if(x < L || x > R) return id;
        if(id == -1) id = ts++;
        if(L == R){
            st[id].v.v1 += v;
            st[id].v.v2 += v;
            return id;
        }
        int M = (L + R) / 2;
        if(x <= M) st[id].l = modify(x, v, L, M, st[id].l);
        else st[id].r = modify(x, v, M + 1, R, st[id].r);
        pull(L, R, id);
        return id;
    }

    Info query(int l, int r, int L = 0, int R = 100000000, int id = 0){
        if(id == -1) return Info();
        if(l <= L && R <= r) return st[id].v;
        int M = (L + R) / 2;
        if(r <= M) return query(l, r, L, M, st[id].l);
        else if(l > M) return query(l, r, M + 1, R, st[id].r);
        else return merge(query(l, r, L, M, st[id].l), query(l, r, M + 1, R, st[id].r), r - M);
    }

    ll query(int x){
        return query(0, x).v2;
    }

};

int main(){
    StarBurstStream

    int n, m;
    cin >> n >> m;

    vector<ll> a(n + 2), b(n + 2);
    for(int i = 1; i <= n; i++) cin >> a[i + 1];
    SparseTableMax stmx(a);
    for(int i = 1; i <= n + 1; i++) a[i] += a[i - 1];
    for(int i = 1; i <= n; i++) cin >> b[i];

    vector<ll> xr(n + 1), xl(n + 2, -1);
    {
        deque<int> dq;
        dq.eb(n + 1);
        for(int i = n; i >= 1; i--){
            while(b[dq.back()] >= b[i]){
                dq.pob;
            }
            xr[i] = a[dq.back()];
            dq.eb(i);
        }
    }
    //cerr << "xr ";
    //printv(xr, cerr);
    
    SparseTable spt(b);

    vector<int> S(m + 1), T(m + 1), U(m + 1);
    vector<ll> ans(m + 1);
    vector<vector<int>> qry(n + 2);
    for(int i = 1; i <= m; i++){
        cin >> S[i] >> T[i] >> U[i];

        if(stmx.query(S[i] + 1, T[i]) > U[i]){
            ans[i] = -1;
            continue;
        }

        qry[S[i]].eb(i);
        int pos = lower_bound(a.begin() + 1, a.end(), max(a[S[i]], a[T[i]] - U[i])) - a.begin();
        int t = spt.query(pos, T[i]);
        //cerr << "test " << i << " " << pos << " " << t << "\n";
        ans[i] += (a[T[i]] - a[t]) * b[t];
        qry[t].eb(-i);
    }

    SegmentTree st;
    auto upd = [&](int i, int t){
        ll pos = xr[i] - a[i];
        st.modify(1, t);
        st.modify(pos + 1, -t);
        //cerr << "upd " << 1 << " " << pos << " " << t << "\n";
        if(xl[i] != -1){
            ll pos2 = a[i] - xl[i];
            st.modify(pos2 + 1, -t);
            ll pos3 = xr[i] - xl[i];
            st.modify(pos3 + 1, t);
            //cerr << "upd " << pos2 + 1 << " " << pos3 << " " << -t << "\n";
        }
        //for(int j = 0; j <= 10; j++) cerr << st.query(j) << " ";
        //cerr << "\n";
    };

    deque<int> dq;
    for(int i = n; i >= 1; i--){
        //cerr << "do " << i << "\n";
        while(!dq.empty() && b[dq.back()] >= b[i]){
            upd(dq.back(), -b[dq.back()]);
            xl[dq.back()] = a[i];
            upd(dq.back(), b[dq.back()]);
            dq.pob;
        }
        dq.eb(i);
        upd(i, b[i]);

        for(int j : qry[i]){
            //cerr << "query " << i << " " << U[abs(j)] << " " << st.query(U[abs(j)]) << "\n";
            if(j > 0) ans[j] += st.query(U[j]);
            else ans[-j] -= st.query(U[-j]);
        }
        
    }

    for(int i = 1; i <= m; i++) cout << ans[i] << "\n";

    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 236512 KB Output is correct
2 Correct 118 ms 236480 KB Output is correct
3 Correct 104 ms 236472 KB Output is correct
4 Correct 102 ms 236432 KB Output is correct
5 Correct 107 ms 236448 KB Output is correct
6 Correct 104 ms 236476 KB Output is correct
7 Correct 118 ms 236460 KB Output is correct
8 Correct 111 ms 236484 KB Output is correct
9 Correct 100 ms 236464 KB Output is correct
10 Correct 108 ms 236484 KB Output is correct
11 Correct 125 ms 236512 KB Output is correct
12 Correct 102 ms 236480 KB Output is correct
13 Correct 104 ms 236544 KB Output is correct
14 Correct 118 ms 236544 KB Output is correct
15 Correct 117 ms 236484 KB Output is correct
16 Correct 116 ms 236536 KB Output is correct
17 Correct 105 ms 236448 KB Output is correct
18 Correct 111 ms 236388 KB Output is correct
19 Correct 106 ms 236544 KB Output is correct
20 Correct 106 ms 236492 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 258932 KB Output is correct
2 Correct 260 ms 258748 KB Output is correct
3 Correct 233 ms 258996 KB Output is correct
4 Correct 189 ms 258860 KB Output is correct
5 Correct 302 ms 258804 KB Output is correct
6 Correct 718 ms 329236 KB Output is correct
7 Correct 863 ms 326608 KB Output is correct
8 Correct 747 ms 330720 KB Output is correct
9 Correct 590 ms 331344 KB Output is correct
10 Correct 773 ms 328288 KB Output is correct
11 Correct 705 ms 326592 KB Output is correct
12 Correct 528 ms 330992 KB Output is correct
13 Correct 1018 ms 328872 KB Output is correct
14 Correct 946 ms 328856 KB Output is correct
15 Correct 742 ms 325708 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1105 ms 326112 KB Output is correct
2 Correct 689 ms 325392 KB Output is correct
3 Correct 568 ms 330180 KB Output is correct
4 Correct 941 ms 327156 KB Output is correct
5 Correct 691 ms 327804 KB Output is correct
6 Correct 671 ms 326012 KB Output is correct
7 Correct 927 ms 327380 KB Output is correct
8 Correct 594 ms 325072 KB Output is correct
9 Correct 418 ms 327076 KB Output is correct
10 Correct 696 ms 326568 KB Output is correct
11 Correct 690 ms 329172 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 236512 KB Output is correct
2 Correct 118 ms 236480 KB Output is correct
3 Correct 104 ms 236472 KB Output is correct
4 Correct 102 ms 236432 KB Output is correct
5 Correct 107 ms 236448 KB Output is correct
6 Correct 104 ms 236476 KB Output is correct
7 Correct 118 ms 236460 KB Output is correct
8 Correct 111 ms 236484 KB Output is correct
9 Correct 100 ms 236464 KB Output is correct
10 Correct 108 ms 236484 KB Output is correct
11 Correct 125 ms 236512 KB Output is correct
12 Correct 102 ms 236480 KB Output is correct
13 Correct 104 ms 236544 KB Output is correct
14 Correct 118 ms 236544 KB Output is correct
15 Correct 117 ms 236484 KB Output is correct
16 Correct 116 ms 236536 KB Output is correct
17 Correct 105 ms 236448 KB Output is correct
18 Correct 111 ms 236388 KB Output is correct
19 Correct 106 ms 236544 KB Output is correct
20 Correct 106 ms 236492 KB Output is correct
21 Correct 258 ms 258932 KB Output is correct
22 Correct 260 ms 258748 KB Output is correct
23 Correct 233 ms 258996 KB Output is correct
24 Correct 189 ms 258860 KB Output is correct
25 Correct 302 ms 258804 KB Output is correct
26 Correct 718 ms 329236 KB Output is correct
27 Correct 863 ms 326608 KB Output is correct
28 Correct 747 ms 330720 KB Output is correct
29 Correct 590 ms 331344 KB Output is correct
30 Correct 773 ms 328288 KB Output is correct
31 Correct 705 ms 326592 KB Output is correct
32 Correct 528 ms 330992 KB Output is correct
33 Correct 1018 ms 328872 KB Output is correct
34 Correct 946 ms 328856 KB Output is correct
35 Correct 742 ms 325708 KB Output is correct
36 Correct 1105 ms 326112 KB Output is correct
37 Correct 689 ms 325392 KB Output is correct
38 Correct 568 ms 330180 KB Output is correct
39 Correct 941 ms 327156 KB Output is correct
40 Correct 691 ms 327804 KB Output is correct
41 Correct 671 ms 326012 KB Output is correct
42 Correct 927 ms 327380 KB Output is correct
43 Correct 594 ms 325072 KB Output is correct
44 Correct 418 ms 327076 KB Output is correct
45 Correct 696 ms 326568 KB Output is correct
46 Correct 690 ms 329172 KB Output is correct
47 Correct 948 ms 328800 KB Output is correct
48 Correct 817 ms 330120 KB Output is correct
49 Correct 640 ms 330688 KB Output is correct
50 Correct 974 ms 328508 KB Output is correct
51 Correct 733 ms 327528 KB Output is correct
52 Correct 813 ms 327608 KB Output is correct
53 Correct 910 ms 328172 KB Output is correct
54 Correct 627 ms 327944 KB Output is correct
55 Correct 536 ms 329916 KB Output is correct
56 Correct 695 ms 326208 KB Output is correct
57 Correct 815 ms 330108 KB Output is correct