Submission #201599

#	Time	Username	Problem	Language	Result	Execution time	Memory
201599		Alexa2001	Fire (JOI20_ho_t5)	C++17	100 / 100	412 ms	35904 KiB

ho_t5

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 2e5 + 5;
typedef long long ll;

int n, q;
int A[Nmax], Prev[Nmax], Next[Nmax], st[Nmax];

ll ans[Nmax];


struct event 
{
    int tip, t, p, w;

    bool operator < (const event &other) const 
    {
        return other.t - t < other.p - p;
    }
};
vector<event>  ev;


struct AIB 
{
    ll a[Nmax], b[Nmax];

    int ub(int x) { return (x&(-x)); }

    
    void upd(ll a[], int pos, ll add)
    {
        for(++pos; pos <= n+1; pos += ub(pos))
            a[pos] += add;
    }

    ll query(ll a[], int pos)
    { 
        ll ans = 0;
        assert(0 <= pos && pos <= n);
        for(++pos; pos; pos -= ub(pos)) ans += a[pos];
        return ans;
    }

public:
    void clear()
    {
        memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b));
    }

    void update(int pos, int w)
    {
        upd(a, pos, w);
        upd(b, pos, -(ll)pos*w + w);
    }

    ll query(int pos)
    {
        return query(a, pos) * pos + query(b, pos);
    }
} aib;

void precalc()
{
    int i, nr = 0;

    for(i=1; i<=n; ++i)
    {
        while(nr && A[st[nr]] < A[i]) --nr;
        
        Prev[i] = st[nr];
        st[++nr] = i;
    }

    nr = 0;
    for(i=n; i; --i)
    {
        while(nr && A[st[nr]] <= A[i]) --nr;

        Next[i] = st[nr];
        st[++nr] = i;
    }
}

void solve()
{
    int i;
    for(i=1; i<=n; ++i)
    {
        ev.push_back({0, 0, i, +A[i]});
        
        if(Prev[i])
            ev.push_back({0, i - Prev[i], i, -A[i]});

        if(Next[i])
            ev.push_back({0, Next[i] - i, Next[i], -A[i]});

        if(Prev[i] && Next[i])
            ev.push_back({0, Next[i] - Prev[i], Next[i], +A[i]});
    }
    
    for(i=1; i<=q; ++i)
    {
        int T, L, R;
        cin >> T >> L >> R;
        
        ev.push_back({1, T, R, i});
        ev.push_back({-1, T, L-1, i});
    }    

    sort(ev.begin(), ev.end());

    aib.clear();
    for(auto it : ev)
        if(it.tip == 0)
            aib.update(it.t, it.w);
        else if(it.tip == 1) 
            ans[it.w] += aib.query(it.t);
        else ans[it.w] -= aib.query(it.t);

    reverse(ev.begin(), ev.end());

    aib.clear();
    for(auto it : ev)
        if(it.tip == 0)
            aib.update(it.p, it.w);
        else if(it.tip == 1)
            ans[it.w] += aib.query(it.p);
        else ans[it.w] -= aib.query(it.p);
}

int main()
{
   // freopen("input", "r", stdin);
    cin.sync_with_stdio(false); cin.tie(0);

    cin >> n >> q;

    int i;
    for(i=1; i<=n; ++i) cin >> A[i];

    precalc();
    solve();

    for(i=1; i<=q; ++i)
        cout << ans[i] << '\n';

    return 0;
}

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