Submission #885589

#	Time	Username	Problem	Language	Result	Execution time	Memory
885589		Pring	Fire (JOI20_ho_t5)	C++14	0 / 100	312 ms	84900 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;

#define ll __int128

const int MXN = 400005;
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;
    ll val[MXN];
    void init(int _n) {
        n = _n;
        fill(val + 1, val + n + 1, 0);
    }
    void modify(int id, ll v) {
        for (; id <= n; id += (id & -id)) val[id] += v;
    }
    ll query(int id) {
        ll ans = 0;
        for (; id > 0; id -= (id & -id)) ans += val[id];
        return ans;
    }
    ll 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, ll v) {
        A.modify(id, v);
        B.modify(id, v * id);
    }
    ll query(int id) {
        return (id + 1) * A.query(id) - B.query(id);
    }
    ll 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, ll v) {
        A.modify(sr + id, v);
    }
    ll query(int id) {
        return A.query(sr + id);
    }
    ll 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, ll v) {
        S.modify(id, v);
        T.modify(id + 1, -v);
    }
    ll query(int id) {
        return S.query(id) + T.query(id);
    }
    ll 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, n) op.push_back(mp(mp(qt[i], 3LL), mp(i, 0LL)));
    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) {
            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) {
        if (ans[i] < 0) ans[i] += (1ULL << 63);
        cout << ans[i] << '\n';
    }
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    miku();
    return 0;
}

Compilation message (stderr)

ho_t5.cpp: In function 'void miku()':
ho_t5.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
ho_t5.cpp:153:13: note: in expansion of macro 'debug'
  153 |             debug("MOVE");
      |             ^~~~~
ho_t5.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
ho_t5.cpp:156:13: note: in expansion of macro 'debug'
  156 |             debug("MODIFY");
      |             ^~~~~
ho_t5.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 39
      |                    ^~
ho_t5.cpp:159:13: note: in expansion of macro 'debug'
  159 |             debug("QUERY");
      |             ^~~~~

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