Submission #1276953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276953		vlomaczk	Fire (JOI20_ho_t5)	C++20	1 / 100	1102 ms	211292 KiB

ho_t5

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

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

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

    SegmentTree(ll _n) {
        n = _n;
        ll lvl = ceil(log2(double(n+1)));
        base = 1<<lvl;
        tree.assign(2*base, 0);
        lazy.assign(2*base, 0);
    }

    void update(ll p, ll k, ll val) {
        Update(1, 0, base-1, p, k, val);
    }
    ll query(ll p, ll k) {
        return Query(1, 0, base-1, p, k);
    }

    void push(ll v, ll a, ll b) {
        if(!lazy[v] || a==b) return;
        ll l = 2*v; ll r = l+1;
        ll len = (b-a+1)/2;
        tree[l] += len*lazy[v];
        tree[r] += len*lazy[v];

        lazy[l] += lazy[v];
        lazy[r] += lazy[v];

        lazy[v] = 0;
    }
    
    void Update(ll v, ll a, ll b, ll p, ll k, ll val) {
        if(b<p || k<a) return;
        if(p<=a && b<=k) {
            tree[v] += (b-a+1)*val;
            lazy[v] += val;
            return;
        }
        ll l = 2*v; ll r = l+1; ll mid = (a+b)/2;
        push(v, a, b);
        Update(l, a, mid, p,k,val);
        Update(r, mid+1, b, p,k,val);
        tree[v] = tree[l] + tree[r];
    }
    
    ll Query(ll v, ll a, ll b, ll p, ll k) {
        if(b<p || k<a) return 0;
        if(p<=a && b<=k) return tree[v];
        ll l = 2*v; ll r = l+1; ll mid = (a+b)/2;
        push(v, a, b);
        return Query(l, a, mid, p,k) + Query(r, mid+1, b, p,k);
    }
};

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

    void use(vector<SegmentTree> &s) {
        s[i].update(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 = 3*n+50; 
    of = 3*n / 2 + 50;
	vector<SegmentTree> s(2, SegmentTree(sn));
	vector<ll> a(n);
	for(ll i=0; i<n; ++i) cin >> a[i];
    vector<ll> ans(q, 0);
	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+2 : i-left[i]), (right[i]==-1 ? n+2 : 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(l+of, r+of) + s[1].query(l-t+of, r-t+of);
        }
    }
    for(ll i=0; i<q; ++i) cout << ans[i] << "\n";

	return 0;
}

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