Submission #653101

#	Time	Username	Problem	Language	Result	Execution time	Memory
653101		someone	Fire (JOI20_ho_t5)	C++14	100 / 100	587 ms	84312 KiB

ho_t5

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

struct Query {
    bool isModif;
    int temps, deb, fin, id, modif;
};

const int M = 1 << 18, N = 2 * M, T = 18, INF = 1e18 + 42;

vector<Query> req;
vector<int> getId[M];
int n, q, print[M], pre[M], aft[M], val[M], a[N], b[N], id[M][2];

void update(int i, int upd, int t) {
    i += M;
    a[i] += upd;
    b[i] -= (t-1) * upd;
    while(i) {
        i >>= 1;
        a[i] = (a[i * 2] + a[i * 2 + 1]);
        b[i] = (b[i * 2] + b[i * 2 + 1]);
    }
}

int getSum(int i, int deb, int fin, int l, int r, int t) {
    if(fin <= l || r <= deb)
        return 0;
    if(l <= deb && fin <= r)
        return a[i] * t + b[i];
    int mid = (deb + fin) / 2;
    return getSum(i*2, deb, mid, l, r, t) + getSum(i*2+1, mid, fin, l, r, t);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> q;
    for(int i = 0; i < n; i++)
        cin >> val[i];
    for(int i = M; i < N; i++)
        a[i] = b[i] = val[i - M];
    for(int i = M-1; i > 0; i--)
        a[i] = b[i] = (a[i * 2] + a[i * 2 + 1]);
    for(int i = 0; i < q; i++) {
        int deb, fin, t;
        cin >> t >> deb >> fin;
        deb--, fin--;
        getId[deb].push_back(i);
        getId[fin].push_back(i);
        id[i][0] = id[i][1] = -1;
        req.push_back({false, t, deb, fin, i, -1});
    }
    deque<int> imax;
    for(int i = 0; i < n; i++) {
        while(!imax.empty() && val[imax[0]] < val[i])
            imax.pop_front();
        if(imax.empty())
            pre[i] = -INF;
        else
            pre[i] = imax[0];
        imax.push_front(i);
        for(int j : getId[i]) {
            int t = req[j].temps, ans = -1;
            for(int k = T-1; k > -1; k--) {
                int x = ans + (1 << k);
                if(x < (int)imax.size() && i - pre[imax[x]] <= t)
                    ans = x;
            }
            ans = imax[ans+1];
            if(id[j][0] == -1)
                id[j][0] = ans;
            else
                id[j][1] = ans;
        }
    }
    imax.clear();
    for(int i = n-1; i > -1; i--) {
        while(!imax.empty() && val[imax.back()] <= val[i])
            imax.pop_back();
        if(imax.empty())
            aft[i] = INF;
        else
            aft[i] = imax.back();
        imax.push_back(i);
    }
    for(int i = 0; i < n; i++) {
        req.push_back({true, i - pre[i], -1, -1, i, -val[i]});
        req.push_back({true, aft[i] - i, -1, -1, i, -val[i]});
        req.push_back({true, aft[i] - pre[i], -1, -1, i, val[i]});
    }
    sort(req.begin(), req.end(),
    [](Query a, Query b) {
        if(a.temps == b.temps)
            return a.isModif && !b.isModif;
        return a.temps < b.temps;
    });
    for(Query q : req) {
        if(q.isModif) {
            update(q.id, q.modif, q.temps);
        } else {
            int deb = id[q.id][0],
                fin = id[q.id][1],
                ans = getSum(1, 0, M, deb+1, fin, q.temps);
            
            q.fin++;
            
            int l = max(q.deb, max(pre[deb] + q.temps + 1, deb)),
                r = min(deb + q.temps + 1, min(aft[deb], q.fin));
            if(l < r)
                ans += val[deb] * (r - l);
            if(deb != fin) {
                l = max(q.deb, max(pre[fin] + q.temps + 1, fin)),
                r = min(fin + q.temps + 1, min(aft[fin], q.fin));
                if(l < r)
                    ans += val[fin] * (r - l);
            }
            print[q.id] = ans;
        }
    }
    for(int i = 0; i < q; i++)
        cout << print[i] << '\n';
}

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