제출 #1181834

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1181834		jerzyk	Fire (JOI20_ho_t5)	C++20	100 / 100	850 ms	86580 KiB

ho_t5

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 1<<19;
ll drz[2][2 * N], laz[2][2 * N];
vector<pair<pair<int, int>, int>> que[N];
vector<pair<pair<int, int>, int>> upd[2][N];

int tab[N], l[N], r[N];
ll answer[N];

void Push(int r, int v)
{
    if(laz[r][v] == 0LL) return;
    for(int s = v * 2; s <= v * 2 + 1; ++s)
    {
        drz[r][s] += laz[r][v] / 2LL;
        laz[r][s] += laz[r][v] / 2LL;
    }
    laz[r][v] = 0LL;
}

void Add(int r, int v, int p, int k, int pz, int kz, ll x)
{
    if(p > kz || k < pz) return;
    if(p >= pz && k <= kz)
    {
        drz[r][v] += (ll)(k - p + 1) * x;
        laz[r][v] += (ll)(k - p + 1) * x;
        return;
    }
    Add(r, v * 2, p, (p + k) / 2, pz, kz, x);
    Add(r, v * 2 + 1, (p + k) / 2 + 1, k, pz, kz, x);
    drz[r][v] = drz[r][v * 2] + drz[r][v * 2 + 1] + laz[r][v];
}

inline void A(int r, int p, int k, int x)
{
    Add(r, 1, 0, N - 1, p, k, x);
}

ll Query(int r, int v, int p, int k, int pz, int kz)
{
    if(p > kz || k < pz) return 0LL;
    if(p >= pz && k <= kz)
        return drz[r][v];
    Push(r, v);
    ll a = Query(r, v * 2, p, (p + k) / 2, pz, kz);
    a += Query(r, v * 2 + 1, (p + k) / 2 + 1, k, pz, kz);
    return a;
}

inline ll Q(int r, int a, int b)
{
    return Query(r, 1, 0, N - 1, a, b);
}

void DoT(int i, int j, int x)
{
    //cout << "T: " << i << " " << j << " " << x << "\n";
    upd[0][j].pb(make_pair(make_pair(i, N - 10), x));
    upd[1][j].pb(make_pair(make_pair((i - j + 1) + (N / 2), N - 10), -x));
}

void Solve()
{
    int n, q, a, b, c;
    cin >> n >> q;
    vector<int> cur = {0};
    tab[0] = II;
    for(int i = 1; i <= n; ++i)
    {
        cin >> tab[i];
        while(tab[i] > tab[cur.back()]) cur.pop_back();
        l[i] = cur.back();
        cur.pb(i);
    }
    tab[n + 1] = II; cur = {n + 1};
    for(int i = n; i >= 1; --i)
    {
        while(tab[i] >= tab[cur.back()]) cur.pop_back();
        r[i] = cur.back();
        cur.pb(i);
    }

    for(int i = 1; i <= q; ++i)
    {
        cin >> c >> a >> b;
        ++c; c = min(c, n);
        que[c].pb(make_pair(make_pair(a, b), i));
    }

    for(int i = 1; i <= n; ++i)
    {
        int d = i - l[i], d2 = r[i] - i;
        //cout << "\nD: " << i << " " << l[i] << " " << r[i] << "\n";
        if(l[i] == 0) d = n;
        DoT(i, 1, tab[i]);

        DoT(i, d + 1, -tab[i]);
        DoT(r[i], d2 + 1, -tab[i]);

        DoT(r[i], d2 + d + 1, tab[i]);
    }
    for(int i = 1; i <= n; ++i)
    {
        for(int r = 0; r < 2; ++r)
            for(int j = 0; j < (int)upd[r][i].size(); ++j)
                A(r, upd[r][i][j].st.st, upd[r][i][j].st.nd, upd[r][i][j].nd);
        for(int j = 0; j < (int)que[i].size(); ++j)
        {
            answer[que[i][j].nd] = Q(0, que[i][j].st.st, que[i][j].st.nd);
            answer[que[i][j].nd] += Q(1, que[i][j].st.st - i + (N / 2), que[i][j].st.nd - i + (N / 2));
        }
    }
    for(int i = 1; i <= q; ++i)
        cout << answer[i] << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

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