Submission #1250219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250219		Thunnus	Pyramid Base (IOI08_pyramid_base)	C++20	65 / 100	2574 ms	271700 KiB

pyramid_base

#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 fi first
#define se second
#define pii pair<int, int>
#define sz(x) (int)(x).size()

const int M = 1e6 + 5;

struct Node{
	int val, len, suff, pref, ans, lazy;
	Node(int v, int l, int s, int p, int a, int lz) : val(v), len(l), suff(s), pref(p), ans(a), lazy(lz) {}
	Node(int l) : Node(0, l, l, l, l, 0) {}
	Node() : Node(0, 0, 0, 0, 0, 0) {}
};

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.len = a.len + b.len;
        if(a.val > b.val){
            c.val = b.val;
            c.ans = b.ans;
            c.pref = 0;
            c.suff = b.suff;
        }
        else if(a.val < b.val){
            c.val = a.val;
            c.ans = a.ans;
            c.pref = a.pref;
            c.suff = 0;
        }
        else{
            c.val = a.val;
            c.suff = b.suff;
            if(b.ans == b.len){
                c.suff = b.ans + a.suff;
            }
            c.pref = a.pref;
            if(a.ans == a.len){
                c.pref = a.ans + b.pref;
            }
            c.ans = max({a.ans, b.ans, a.suff + b.pref});
        }
        return c;
    }
    
    inline void build(int v, int tl, int tr){ // wtf???????
		if(tl == tr){
			st[v] = Node(1);
			return;
		}
		int mid = (tl + tr) / 2;
		build(2 * v, tl, mid);
		build(2 * v + 1, mid + 1, tr);
		st[v] = combine(st[2 * v], st[2 * v + 1]);
		return;
	}
	
	inline void build(){
		build(1, 1, n);
		return;
	}

    inline void apply(int v, int val){
        st[v].val += val;
        st[v].lazy += val;
        return;
    }

    inline void propagate(int v){
        apply(2 * v, st[v].lazy);
        apply(2 * v + 1, st[v].lazy);
        st[v].lazy = 0;
        return;
    }

    inline void update(int ul, int ur, int val, int v, int tl, int tr){
        if(ul > tr || tl > ur) return;
        if(ul <= tl && tr <= ur){
            apply(v, val);
            return;
        }
        int mid = (tl + tr) / 2;
        propagate(v);
        update(ul, ur, val, 2 * v, tl, mid);
        update(ul, ur, val, 2 * v + 1, mid + 1, tr);
        st[v] = combine(st[2 * v], st[2 * v + 1]);
        return;
    }

    inline void update(int ul, int ur, int val){
		if(ul > ur) return;
        update(max(ul + 1, 1ll), min(ur + 1, n), val, 1, 1, n);
        return;
    }
};

inline void solve(){
    int m, n, budget, p;
    cin >> n >> m >> budget >> p;
    vector<array<int, 5>> ob(p);
    for(int i = 0; i < p; i++){ // {x1, y1, x2, y2, c}
        cin >> ob[i][0] >> ob[i][1] >> ob[i][2] >> ob[i][3] >> ob[i][4];
        ob[i][0]--, ob[i][1]--, ob[i][2]--, ob[i][3]--;
    }

    auto solve0 = [&]() -> int {
        vvi add(n), er(n);
        for(int i = 0; i < p; i++){
            add[ob[i][0]].emplace_back(i);
            er[ob[i][2]].emplace_back(i);
        }

        int ans = 0;
        SegTree st(m);
        st.build();
        for(int le = 0, ri = -1; le < n; le++){
            while(ri < n){
                if(st.st[1].val || st.st[1].ans < ri - le + 1) break;
                ri++;
                for(int &idx : add[ri]){
                    array<int, 5> r = ob[idx];
                    st.update(r[1], r[3], 1);
                }
            }
            ans = max(ans, (ri - 1) - le + 1); // just before the last addition on ri
            for(int &idx : er[le]){
                array<int, 5> r = ob[idx];
                st.update(r[1], r[3], -1);
            }
        }
        return ans;
    };

    auto solve1 = [&]() -> int {
        auto check = [&](int len) -> bool {
			//cout << "len: " << len << "\n";
            vvi pos(n + 1);
            SegTree st(m - len + 1);
            for(int i = 0; i < p; i++){
                int lx = max(ob[i][0] - len + 1, 0ll), rx = ob[i][2];
                pos[lx].emplace_back(i), pos[rx + 1].emplace_back(i);
            }
            for(int i = 0; i < n - len + 1; i++){
                for(int &idx : pos[i]){
                    int dy = max(ob[idx][1] - len + 1, 0ll), uy = ob[idx][3], c = (i == ob[idx][2] + 1 ? -ob[idx][4] : ob[idx][4]);
                    //cout << "idx: " << idx << " dy: " << dy << " uy: " << uy << " c: " << c << "\n";
                    st.update(dy, uy, c);
                }
                if(st.st[1].val <= budget) return true;
            }
            return false;
        };

        auto bs = [&]() -> int {
            int lo = 1, hi = min(n, m), ret = 0, mid;
            while(hi >= lo){
                mid = lo + (hi - lo) / 2;
                if(check(mid)){
                    lo = mid + 1;
                    ret = mid;
                }
                else{
                    hi = mid - 1;
                }
            }
            return ret;
        };
        return bs();
    };
    
    cout << (budget ? solve1() : solve0()) << "\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: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7
• Subtask 11: 7 / 7
• Subtask 12: 7 / 7
• Subtask 13: 10 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10