제출 #1276939

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

ho_t5

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

ll n,q,sn,of;
ll M = 200'000;

struct SegmentTree {
    ll n;
    vector<long long> tree, lazy;

    SegmentTree(ll _n) {
        n = _n;
        tree.assign(4 * n, 0);
        lazy.assign(4 * n, 0);
    }

    void build(vector<long long> &arr, ll v, ll tl, ll tr) {
        if (tl == tr) {
            tree[v] = arr[tl];
        } else {
            ll tm = (tl + tr) / 2;
            build(arr, v * 2, tl, tm);
            build(arr, v * 2 + 1, tm + 1, tr);
            tree[v] = tree[v * 2] + tree[v * 2 + 1];
        }
    }

    void push(ll v, ll tl, ll tr) {
        if (lazy[v] != 0) {
            tree[v] += lazy[v] * (tr - tl + 1);
            if (tl != tr) {
                lazy[v * 2] += lazy[v];
                lazy[v * 2 + 1] += lazy[v];
            }
            lazy[v] = 0;
        }
    }

    void update(ll v, ll tl, ll tr, ll l, ll r, long long addend) {
        push(v, tl, tr);
        if (l > r) return;
        if (l == tl && r == tr) {
            lazy[v] += addend;
            push(v, tl, tr);
        } else {
            ll tm = (tl + tr) / 2;
            update(v * 2, tl, tm, l, min(r, tm), addend);
            update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, addend);
            tree[v] = tree[v * 2] + tree[v * 2 + 1];
        }
    }

    long long query(ll v, ll tl, ll tr, ll l, ll r) {
        if (l > r) return 0;
        push(v, tl, tr);
        if (l <= tl && tr <= r) {
            return tree[v];
        }
        ll tm = (tl + tr) / 2;
        return query(v * 2, tl, tm, l, min(r, tm))
             + query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
    }
};

struct query {
    ll l,r,x,i;

    void use(vector<SegmentTree> &s) {
        s[i].update(1, 0, sn-1, l, r, x);
    }
};

vector<vector<query>> events(4*M);

void add_triangle(ll i, ll w, ll x) {
    query q1_s = {i+w+of, sn-1, -x, 0};
    query q1_e = q1_s; q1_e.x *= -1;
    
    query q2_s = {i-1+of, sn-1, x, 1};
    query q2_e = q2_s; q2_e.x *= -1;

    events[1].push_back(q1_s); events[1].push_back(q2_s);
    events[w+1].push_back(q1_e); events[w+1].push_back(q2_e);
}

void add_rownoleglobok(ll i, ll wys, ll dl, ll x) {
    add_triangle(i+1, dl-1, -x);
    add_triangle(i-wys+1, wys-1, -x);
    add_triangle(i-wys+1, wys+dl-1, x);
}

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

	cin >> n >> q;
	sn = 4*n+5;
    of = 3*n / 2;
	vector<SegmentTree> s(2, SegmentTree(sn));
	vector<ll> a(n);
	for(ll i=0; i<n; ++i) cin >> a[i];
    vector<ll> ans(q);
	vector<pair<ll, ll>> queries;
	vector<vector<ll>> buckets(n+2);
	for(ll i=0; i<q; ++i) {
		ll l,r,t;
		cin >> t >> l >> r;
        ++t;
		queries.emplace_back(l,r);
		buckets[t].push_back(i);
	}
    stack<ll> stos;
    vector<ll> left(n, -1), right(n, -1);
    for(ll i=0; i<n; ++i) {
        while(stos.size() && a[stos.top()] < a[i]) stos.pop();
        if(stos.size()) left[i] = stos.top();
        stos.push(i);
    }
    while(stos.size()) stos.pop();
    for(ll i=n-1; i>=0; --i) {
        while(stos.size() && a[stos.top()] <= a[i]) stos.pop();
        if(stos.size()) right[i] = stos.top();
        stos.push(i);
    }
    for(ll i=0; i<n; ++i) {
        add_rownoleglobok(i+1, (left[i]==-1 ? n : i-left[i]), (right[i]==-1 ? n : right[i]-i), a[i]);
    }
    for(ll t=1; t<=n+1; ++t) {
        for(auto &x : events[t]) x.use(s);
        for(auto i : buckets[t]) {
            auto[l, r] = queries[i];
            ans[i] = s[0].query(1, 0, sn-1, l+of, r+of) + s[1].query(1, 0, sn-1, l-t+of, r-t+of);
        }
    }
    for(ll i=0; i<q; ++i) cout << ans[i] << "\n";

	return 0;
}

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