Submission #1256453

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256453		Thunnus	Food Court (JOI21_foodcourt)	C++20	100 / 100	392 ms	66060 KiB

foodcourt

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

struct Node{
    int sum, min;
    Node(int sm, int mn) : sum(sm), min(mn) {}
    Node() : Node(0ll, 0ll) {}
};

struct SegTree{
    int n;
    vector<Node> st;
    SegTree(int n) : n(n), st(4 * n) {}

    inline Node combine(const Node &a, const Node &b){
        Node c;
        c.sum = a.sum + b.sum;
        c.min = min(a.min, b.min + a.sum);
        return c;
    }

    inline void update(int pos, int val, int v, int tl, int tr){
        if(tl == tr){
            st[v].sum += val;
            st[v].min = min(st[v].sum, 0ll); // minimum prefix sum
            return;
        }
        int mid = (tl + tr) / 2;
        if(pos <= mid){
            update(pos, val, 2 * v, tl, mid);
        }
        else{
            update(pos, val, 2 * v + 1, mid + 1, tr);
        }
        st[v] = combine(st[2 * v], st[2 * v + 1]);
        return;
    }

    inline void update(int pos, int val){
        update(pos + 1, val, 1, 1, n);
    }

    inline Node query(int ql, int qr, int v, int tl, int tr){
        if(ql > tr || tl > qr) return Node();
        if(ql <= tl && tr <= qr) return st[v];
        int mid = (tl + tr) / 2;
        return combine(query(ql, qr, 2 * v , tl, mid), query(ql, qr, 2 * v + 1, mid + 1, tr));
    }

    inline Node query(int ql, int qr){
        return query(ql + 1, qr + 1, 1, 1, n);
    }

    inline int walk(int k, int v, int tl, int tr){
        if(tl == tr) return tl - 1;
        int mid = (tl + tr) / 2;
        if(k >= st[2 * v].sum){
            k -= st[2 * v].sum; 
            return walk(k, 2 * v + 1, mid + 1, tr);
        }
        else{
            return walk(k, 2 * v, tl, mid);
        }    
    }
    
    inline int walk(int k){
		return walk(k, 1, 1, n);
	}
};

inline void solve(){
    int n, m, q;
    cin >> n >> m >> q;
    vi groups(q), ans(q, -1);
    vector<vector<pii>> queries(n + 1), add(n + 1), del(n + 1);
    for(int i = 0; i < q; i++){
        int type, l, r, c, k;
        cin >> type;
        if(type == 1){
            cin >> l >> r >> c >> k;
            l--, r--;
            groups[i] = c;
            add[l].emplace_back(k, -i);
            add[r + 1].emplace_back(-k, -i);
        }
        else if(type == 2){
            cin >> l >> r >> k;
            l--, r--;
            del[l].emplace_back(-k, -i);
            del[r + 1].emplace_back(k, -i);
        }
        else{
            cin >> l >> r;
            l--;
            queries[l].emplace_back(r, i);
        }
    }

    SegTree st(q), sm(q);
    for(int i = 0; i < n; i++){
        for(pii &ad : add[i]){
			//cout << "i: " << i << " ad: " << -ad.se << " " << ad.fi << "\n";
            st.update(-ad.se, ad.fi);
            sm.update(-ad.se, ad.fi);
        }
        for(pii &de : del[i]){
			//cout << "i: " << i << " de: " << -de.se << " " << de.fi << "\n"; 
            st.update(-de.se, de.fi);
        }
        for(pii &qu : queries[i]){
            Node left = st.query(0, qu.se); // plus - minus
            //cout << "i: " << i << " qu: " << qu.fi << " " << qu.se << " left: " << left.sum << " " << left.min << "\n";
            if(left.sum - left.min >= qu.fi){
                int minus = sm.query(0, qu.se).sum - (left.sum - left.min); // plus - (plus - minus) = minus
                int idx = sm.walk(qu.fi + minus - 1);
                ans[qu.se] = groups[idx];
            }
            else{
                ans[qu.se] = 0;
            }
        }
    }

    for(int i = 0; i < q; i++){
        if(ans[i] == -1) continue;
        cout << ans[i] << "\n";
    }
    cout << "\n";
    return;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
	return 0;
}

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