Submission #1086604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086604		_callmelucian	Fire (JOI20_ho_t5)	C++14	100 / 100	605 ms	92784 KiB

ho_t5

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 4e5 + 5;
ll a[mn], lb[mn], rb[mn], small[mn], big[mn], all[mn], ans[mn];
vector<pii> event[mn];
vector<tt> qry[mn];

struct BIT {
    vector<ll> tr;
    BIT (int sz) : tr(sz + 1) {}

    int p (int k) { return k & -k; }

    void update (int k, ll val) {
        for (; k < tr.size(); k += p(k)) tr[k] += val;
    }

    ll preSum (int k, ll ans = 0) {
        for (; k; k -= p(k)) ans += tr[k];
        return ans;
    }

    int get (int k) { return tr[k]; }
} cntOne(mn), sumOne(mn), freqTwo(mn), sumTwo(mn), cntThree(mn), freqThree(mn), sumThree(mn), sumFreqThree(mn);

int cntGet (int k, int T) {
    return cntOne.get(k) * (T + 1) + freqTwo.get(k) + freqThree.get(k) - cntThree.get(k) * T;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, q; cin >> n >> q;
    for (int i = n + 1; i <= 2 * n; i++) cin >> a[i];
    for (int i = 0; i < q; i++) {
        int T, L, R; cin >> T >> L >> R;
        qry[T].emplace_back(n + L - 1 - T, i, -1);
        qry[T].emplace_back(n + R - T, i, 1);
    }

    a[0] = a[2 * n + 1] = INT_MAX;
    stack<int> st;

    st.push(0);
    for (int i = 1; i <= 2 * n; i++) {
        while (make_pair(a[st.top()], st.top()) <= make_pair(a[i], i)) st.pop();
        lb[i] = st.top() + 1; st.push(i);
    }

    while (st.size()) st.pop(); st.push(2 * n + 1);
    for (int i = 2 * n; i >= 1; i--) {
        while (make_pair(a[st.top()], st.top()) <= make_pair(a[i], i)) st.pop();
        rb[i] = st.top() - 1; st.push(i);
    }

    for (int i = 1; i <= 2 * n; i++) {
        small[i] = i - lb[i] + 1, big[i] = rb[i] - i + 1;
        all[i] = rb[i] - lb[i] + 1;
        if (small[i] > big[i]) swap(small[i], big[i]);

        event[small[i]].emplace_back(i, 1); // switch to small[i]
        event[big[i]].emplace_back(i, 2); // switch to all[i] - T
        event[all[i]].emplace_back(i, 3); // switch to 0

        cntOne.update(i, 1);
        sumOne.update(i, a[i]);
    }

    for (int T = 1; T <= n; T++) {
        for (pii it : event[T]) {
            int pos, type; tie(pos, type) = it;
            if (type == 1) {
                cntOne.update(pos, -1);
                sumOne.update(pos, -a[pos]);

                freqTwo.update(pos, small[pos]);
                sumTwo.update(pos, a[pos] * small[pos]);
            }
            else if (type == 2) {
                freqTwo.update(pos, -small[pos]);
                sumTwo.update(pos, -a[pos] * small[pos]);

                cntThree.update(pos, 1);
                freqThree.update(pos, all[pos]);
                sumThree.update(pos, a[pos]);
                sumFreqThree.update(pos, a[pos] * all[pos]);
            }
            else if (type == 3) {
                cntThree.update(pos, -1);
                freqThree.update(pos, -all[pos]);
                sumThree.update(pos, -a[pos]);
                sumFreqThree.update(pos, -a[pos] * all[pos]);
            }
        }

        for (tt it : qry[T]) {
            int P, id, multi; tie(P, id, multi) = it;

            int ub = 0, cur = 0;
            for (int msk = 1 << 18; msk > 0; msk >>= 1)
                if ((ub | msk) <= 2 * n && cur + cntGet(ub | msk, T) <= P)
                    ub |= msk, cur += cntGet(ub, T);

            ll accumulated = sumOne.preSum(ub) * (T + 1) + sumTwo.preSum(ub) + sumFreqThree.preSum(ub) - sumThree.preSum(ub) * T;
            if (ub < 2 * n) accumulated += a[ub + 1] * (P - cur);
            ans[id] += accumulated * multi;
        }
    }

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


    return 0;
}

Compilation message (stderr)

ho_t5.cpp: In member function 'void BIT::update(int, ll)':
ho_t5.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for (; k < tr.size(); k += p(k)) tr[k] += val;
      |                ~~^~~~~~~~~~~
ho_t5.cpp: In function 'int main()':
ho_t5.cpp:62:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   62 |     while (st.size()) st.pop(); st.push(2 * n + 1);
      |     ^~~~~
ho_t5.cpp:62:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   62 |     while (st.size()) st.pop(); st.push(2 * n + 1);
      |                                 ^~

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