제출 #1185086

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1185086		patgra	Fire (JOI20_ho_t5)	C++20	0 / 100	494 ms	169364 KiB

ho_t5

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

int n, q;
vector<int> iniFire;
vector<pair<pair<int, int>, pair<int, int>>> queries;
vector<pair<pair<int, int>, pair<int, int>>> events;
vector<pair<pair<int, int>, int>> triangles;
vector<vector<int>> stMax;
int tb, maxLog;
vector<ll> tr, lz;
vector<ll> answers;

int stMaxQ(int l, int r) {
    int k = 31 - __builtin_clz(r - l + 1);
    return max(stMax[l][k], stMax[r - (1 << k) + 1][k]);
}

void push(int v, int cnt) {
    tr[2 * v] += lz[v] * cnt / 2;
    lz[2 * v] += lz[v];
    tr[2 * v + 1] += lz[v] * cnt / 2;
    lz[2 * v + 1] += lz[v];
    lz[v] = 0;
}

void tAdd(int l, int r, ll x, int mL, int mR, int v) {
    if(v == 1) DC << "  tAdd( " << l << ' ' << r << ' ' << x << ')' << eol;
    if(l > mR || mL > r) return;
    if(l <= mL && mR <= r) {
        tr[v] += x * (mR - mL + 1);
        lz[v] += x;
        return;
    }
    push(v, mR - mL + 1);
    tAdd(l, r, x, mL, (mL + mR) / 2, 2 * v);
    tAdd(l, r, x, (mL + mR) / 2 + 1, mR, 2 * v + 1);
    tr[v] = tr[2 * v] + tr[2 * v + 1];
}

ll tQuery(int l, int r, int mL, int mR, int v) {
    if(v == 1) DC << "  tQuery( " << l << ' ' << r << ")  ->  ";
    if(l > mR || mL > r) return 0;
    if(l <= mL && mR <= r) return tr[v];
    push(v, mR - mL + 1);
    auto a = tQuery(l, r, mL, (mL + mR) / 2, 2 * v);
    auto b = tQuery(l, r, (mL + mR) / 2 + 1, mR, 2 * v + 1);
    if(v == 1) DC << a + b << eol;
    return a + b;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> q;
    iniFire.resize(n);
    queries.resize(q);
    answers.resize(q);
    maxLog = 32 - __builtin_clz(n);
    tb = 16 << maxLog;
    stMax.resize(n, vector<int>(maxLog));
    tr.resize(2 * tb); lz.resize(2 * tb);
    rep(i, 0, n) cin >> iniFire[i];
    rep(i, 0, q) {
        int x, y, z;
        cin >> x >> y >> z;
        y--; z--;
        queries[i] = {{x, i}, {y, z}};
    }

    ranges::sort(queries);
    rep(i, 0, n) stMax[i][0] = iniFire[i];
    rep(k, 1, maxLog) rep(i, 0, n) stMax[i][k] = max(stMax[i][k - 1], stMax[min(n - 1, i + (1 << (k - 1)))][k - 1]);
    rep(i, 0, n) {
        int l = -1, r = i, m;
        while(r - l > 1) {
            m = (l + r) / 2;
            (stMaxQ(m, i - 1) >= iniFire[i] ? l : r) = m;
        }
        int L = l;
        l = i, r = n;
        while(r - l > 1) {
            m = (l + r) / 2;
            (stMaxQ(i + 1, m) > iniFire[i] ? r : l) = m;
        }
        int R = r;
        if(L == -1) L = -2 * n;
        if(R == n) R = 2 * n;
        l = i - L;
        r = R - i;
        DC << " i " << i << " L " << L << " R " << R << " l " << l << " r " << r << eol;
        triangles.pb({{r - 2, R - 1}, -iniFire[i]});
        triangles.pb({{l - 2, i - 1}, -iniFire[i]});
        triangles.pb({{l + r - 2, R - 1}, iniFire[i]});
    }
    ranges::sort(triangles);
    ranges::reverse(triangles); ranges::reverse(queries);
    DEBUG {
        DC << "Triangles: " << eol;
        repIn2(timex, add, triangles) DC << " (" << timex.first << ' ' << timex.second << ") += " << add << eol;
    }

    int ti = 0;
    repIn2(timeqi, lr, queries) {
        auto [time, qi] = timeqi;
        auto [l, r] = lr;
        while(ti < (int)triangles.size() && triangles[ti].first.first >= time) {
            auto wher = triangles[ti].first.second;
            auto x = triangles[ti].second;
            if(wher >= 0) tAdd(0, wher, x, 0, tb - 1, 1);
            ti++;
        }
        answers[qi] += tQuery(l, r, 0, tb - 1, 1);
    }

    DEBUG {
        DC << "After rectangels:" << eol;
        rep(i, 0, q) DC << ' ' << answers[i] << eol;
    }

    rep(i, 0, 2 * tb) tr[i] = lz[i] = 0;

    ti = 0;
    repIn2(timeqi, lr, queries) {
        auto [time, qi] = timeqi;
        auto [l, r] = lr;
        while(ti < (int)triangles.size() && triangles[ti].first.first >= time) {
            auto wher = triangles[ti].first.second;
            auto x = triangles[ti].second;
            wher--;
            if(wher + n * n - triangles[ti].first.first >= 0) tAdd(0, wher + n * n - triangles[ti].first.first, x, 0, tb - 1, 1);
            ti++;
        }
        answers[qi] -= tQuery(l + n * n - time, r + n * n - time, 0, tb - 1, 1);
    }

    rep(i, 0, q) cout << answers[i] << '\n';
}

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