Submission #1309647

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309647		vlomaczk	Food Court (JOI21_foodcourt)	C++20	20 / 100	1097 ms	66080 KiB

foodcourt

#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>;

const ll INF = 1e18;

struct SegmentTreeBeats {
    ll n, base;
    vector<ll> val, add_lazy;

    SegmentTreeBeats(ll n_) {
        n = n_;
        base = 1;
        while (base < n) base <<= 1;
        val.assign(base * 2, 0);
        add_lazy.assign(base * 2, 0);
    }

    void push(ll node, ll l, ll r) {
        if (add_lazy[node] != 0 && l != r) {
            ll mid = (l + r) / 2;
            val[node*2] += add_lazy[node];
            add_lazy[node*2] += add_lazy[node];
            val[node*2+1] += add_lazy[node];
            add_lazy[node*2+1] += add_lazy[node];
            add_lazy[node] = 0;
        }
    }

    void update(ll node, ll l, ll r, ll ql, ll qr, ll x) {
        if (ql > r || qr < l) return;
        if (ql <= l && r <= qr) {
            val[node] += x;
            add_lazy[node] += x;
            return;
        }
        push(node,l,r);
        ll mid = (l+r)/2;
        update(node*2, l, mid, ql, qr, x);
        update(node*2+1, mid+1, r, ql, qr, x);
        val[node] = min(val[node*2], val[node*2+1]);
    }

    void max_with(ll node, ll l, ll r, ll x) {
        if (val[node] >= x) return; // All already >= x
        if (l == r) {
            val[node] = max(val[node], x);
            return;
        }
        push(node, l, r);
        ll mid = (l+r)/2;
        max_with(node*2, l, mid, x);
        max_with(node*2+1, mid+1, r, x);
        val[node] = min(val[node*2], val[node*2+1]);
    }

    ll query(ll node, ll l, ll r, ll pos) {
        if (l == r) return val[node];
        push(node, l, r);
        ll mid = (l+r)/2;
        if (pos <= mid) return query(node*2, l, mid, pos);
        else return query(node*2+1, mid+1, r, pos);
    }

    // Public API
    void add(ll l, ll r, ll x) { update(1,0,base-1,l,r,x); }
    void max_with_zero() { max_with(1,0,base-1,0); }
    ll query(ll pos) { return query(1,0,base-1,pos); }
};

struct Block {
	ll type,amount,time;
};

struct SegTree {
    ll base;
    vector<ll> T, L;

    SegTree(ll n) {
        ll lvl = __lg(n) + 1;
        base = 1<<lvl;
        T.assign(2*base, 0);
        L.assign(2*base, 0);
    }

    void push(ll v, ll l, ll r) {
        if(L[v]==0 || r>=2*base) return;
        T[l] += L[v];
        T[r] += L[v];

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

        L[v] = 0;
    }

    void update(ll v, ll a, ll b, ll l, ll r, ll val) {
        if(b < l || r < a) return;
        if(l<=a && b<=r) {
            T[v] += val;
            L[v] += val;
            return;
        }
        ll lewy = 2*v; ll prawy = 2*v+1; ll mid=(a+b)/2;
        push(v, lewy, prawy);
        update(lewy,a,mid,l,r,val);
        update(prawy,mid+1,b,l,r,val);
        T[v] = max(T[lewy], T[prawy]);
    }

    ll find(ll v, ll a, ll b, ll x) {
        if(a==b) return v - base;
        ll lewy = 2*v; ll prawy = 2*v+1; ll mid=(a+b)/2;
        push(v, lewy, prawy);
        if(T[lewy] >= x) return find(lewy,a,mid,x);
        return find(prawy,mid+1,b,x);
    }
};

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

	ll n,m,q;
	cin >> n >> m >> q;
	vector<ll> ans;
	vector<vector<pair<ll, ll>>> query(n+1);
	vector<vector<Block>> bloki_add(n+1), bloki_del(n+2);
	SegmentTreeBeats stb(n), stb2(n);
	for(ll t=0; t<q; ++t) {
		ll T; cin >> T;
		if(T==1) {
			ll l,r,c,k;
			cin >> l >> r >> c >> k;
            --l; --r;
			bloki_add[l].push_back({c,k,t});
            bloki_del[r+1].push_back({c,k,t});
			stb.add(l,r,k);
			stb2.add(l,r,k);
		} else if(T==2) {
			ll l,r,k;
			cin >> l >> r >> k;
            --l; --r;
			stb.add(l,r,-k);
		} else {
			ll a,b;
			cin >> a >> b;
            --a;
			ans.push_back(-1);
			if(stb.query(a) < b) ans.back() = 0;
			else {
                query[a].push_back({b + stb2.query(a) - stb.query(a), ans.size()-1});
            }
		}
		stb.max_with_zero();
    }
    SegTree st(2*q);
    vector<ll> typ(2*q+1, -1);
    for(ll i=0; i<n; ++i) {
        for(auto[c,k,t] : bloki_add[i]) {
            typ[t] = c;
            st.update(1,0,st.base-1,t,st.base-1,k);
        }   
        for(auto[c,k,t] : bloki_del[i]) {
            typ[t] = -1;
            st.update(1,0,st.base-1,t,st.base-1,-k);
        }
        for(auto[poz, idx] : query[i]) {

            ans[idx] = typ[st.find(1,0,st.base-1,poz)];
        }
    }
	for(auto x : ans) cout << x << '\n';

	return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 21
• Subtask 5: 0 / 15
• Subtask 6: 13 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11