Submission #885600

#	Time	Username	Problem	Language	Result	Execution time	Memory
885600		Pring	Fire (JOI20_ho_t5)	C++14	100 / 100	274 ms	94568 KiB

ho_t5

#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
#define debug(x...) cout << '[' << #x << "] : ", dout(x)
void dout() { cout << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i,j,k) for (int i = j, Z = k; i <= Z; i++)
typedef pair<int, int> pii;
typedef pair<pii, pii> p4i;

const int MXN = 1000005;
int n, q, a[MXN], l[MXN], r[MXN], ans[MXN];
int ql[MXN], qr[MXN], qt[MXN];
vector<p4i> op;

struct BIT {
    int n;
    int val[MXN];
    void init(int _n) {
        n = _n;
        fill(val + 1, val + n + 1, 0);
    }
    void modify(int id, int v) {
        for (; id <= n; id += (id & -id)) val[id] += v;
    }
    int query(int id) {
        int ans = 0;
        for (; id > 0; id -= (id & -id)) ans += val[id];
        return ans;
    }
    int query(int l, int r) {
        return query(r) - query(l - 1);
    }
};

struct BBIT {
    BIT A, B;
    void init(int _n) {
        A.init(_n);
        B.init(_n);
    }
    void modify(int id, int v) {
        A.modify(id, v);
        B.modify(id, v * id);
    }
    int query(int id) {
        return (id + 1) * A.query(id) - B.query(id);
    }
    int query(int l, int r) {
        return query(r) - query(l - 1);
    }
};

struct HBBIT {
    BBIT A;
    int sr;
    void init(int _n) {
        A.init(_n * 2);
        sr = _n;
    }
    void move() {
        sr--;
    }
    void modify(int id, int v) {
        A.modify(sr + id, v);
    }
    int query(int id) {
        return A.query(sr + id);
    }
    int query(int l, int r) {
        return query(r) - query(l - 1);
    }
};

struct DS {
    BBIT S;
    HBBIT T;
    void init(int _n) {
        S.init(_n);
        T.init(_n);
    }
    void move() {
        T.move();
    }
    void modify(int id, int v) {
        S.modify(id, v);
        T.modify(id + 1, -v);
    }
    int query(int id) {
        return S.query(id) + T.query(id);
    }
    int query(int l, int r) {
        return query(r) - query(l - 1);
    }
} B;

void FIND_L() {
    stack<pii> st;
    st.push(mp(LLONG_MAX, -1LL));
    for (int i = 1; i <= n; i++) {
        while (st.top().fs <= a[i]) st.pop();
        l[i] = st.top().sc;
        st.push(mp(a[i], i));
    }
}

void FIND_R() {
    stack<pii> st;
    st.push(mp(LLONG_MAX, -1LL));
    for (int i = n; i > 0; i--) {
        while (st.top().fs < a[i]) st.pop();
        r[i] = st.top().sc;
        st.push(mp(a[i], i));
    }
}

void BOX(int id) {
    op.push_back(mp(mp(0LL, 2LL), mp(id, a[id])));
    if (l[id] != -1) op.push_back(mp(mp(id - l[id], 2LL), mp(id, -a[id])));
    if (r[id] != -1) op.push_back(mp(mp(r[id] - id, 2LL), mp(r[id], -a[id])));
    if (l[id] != -1 && r[id] != -1) op.push_back(mp(mp(r[id] - l[id], 2LL), mp(r[id], a[id])));
}

void BOX() {
    FOR(i, 1, n) op.push_back(mp(mp(i, 1LL), mp(0LL, 0LL)));
    FOR(i, 1, n) BOX(i);
    FOR(i, 1, q) op.push_back(mp(mp(qt[i], 3LL), mp(i, 0LL)));
    // op.push_back(mp(mp(0LL, 2LL), mp(3LL, 2LL)));
    // op.push_back(mp(mp(3LL, 2LL), mp(6LL, -2LL)));
    sort(op.begin(), op.end());
}

void miku() {
    cin >> n >> q;
    FOR(i, 1, n) cin >> a[i];
    FOR(i, 1, q) cin >> qt[i] >> ql[i] >> qr[i];
    FIND_L();
    FIND_R();
    BOX();
    B.init(n);
    for (auto &i : op) {
        if (i.fs.sc == 1) {
            // FOR(i, 1, n) cout << B.query(i, i) << ' ';
            // cout << endl;
            // debug("MOVE");
            B.move();
        } else if (i.fs.sc == 2) {
            // debug("MODIFY");
            B.modify(i.sc.fs, i.sc.sc);
        } else {
            // debug("QUERY");
            int id = i.sc.fs;
            ans[id] = B.query(ql[id], qr[id]);
        }
    }
    FOR(i, 1, q) {
        cout << ans[i] << '\n';
    }
}

void RESET() {
    FOR(i, 1, n) {
        a[i] = 0;
        l[i] = 0;
        r[i] = 0;
    }
    FOR(i, 1, q) {
        ans[i] = 0;
        ql[i] = 0;
        qr[i] = 0;
        qt[i] = 0;
    }
    op.clear();
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    int t = 1;
    // cin >> t;
    while (t--) {
        miku();
        // RESET();
    }
    return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 80 / 80