Submission #1000606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000606		theboatman	Pyramid Base (IOI08_pyramid_base)	C++17	90 / 100	5056 ms	65480 KiB

pyramid_base

#include <bits/stdc++.h>

using namespace std;

int n, m, p;
int budget;
vector <int> x, y, x2, y2, cost;

struct UpdateQuery {
    int x, l, r, add;
    //UpdateQuery(int a, int b, int c, int d) : x(a), l(b), r(c), add(d) {}
};

struct SegmentTree {
    int v;
    int tl;
    int tr;
    vector <int> t;
    vector <int> push;

    SegmentTree(int n) : v(1), tl(1), tr(n) {
        t.resize(4 * n);
        push.resize(4 * n);
    };

    void add(int l, int r, int incVal) {
        update(v, tl, tr, l, r, incVal);
    }

    int get() {
        return t[v];
    }

    private:
    void update(int v, int tl, int tr, int l, int r, int incVal) { 
        if (l > r) {
            return;
        }

        if (tl == l && tr == r) {
            t[v] += incVal;
            push[v] += incVal;
            return;
        }

        if (push[v]) {
            t[v << 1] += push[v];
            t[v << 1 | 1] += push[v];

            if (tl != tr) {
                push[v << 1] += push[v];
                push[v << 1 | 1] += push[v];
            }
            
            push[v] = 0;
        }

        int tm = tl + tr >> 1;
        update(v << 1, tl, tm, l, min(r, tm), incVal);
        update(v << 1 | 1, tm + 1, tr, max(tm + 1, l), r, incVal);

        t[v] = min(t[v << 1], t[v << 1 | 1]);
    }
};

UpdateQuery q[(int)(1e6)];

int getCost(int len) {
    int N = n - len + 1;
    int M = m - len + 1;

    int stn = 0;
    for (int i = 0; i < p; i++) {
        int _x = x[i] - len + 1;
        int _y = y[i] - len + 1;

        _x = max(_x, 1);
        _y = max(_y, 1);

        int _y1 = min(y2[i], M);

        if (_y > M) {
            continue;
        }

        q[stn++] = {_x, _y, _y1, cost[i]};
        if (x2[i] + 1 <= N) {
            q[stn++] = {x2[i] + 1, _y, _y1, -cost[i]};
        }
    }
    
    q[stn++] = {1, 1, 1, 0};
    sort(q, q + stn, [](const UpdateQuery &a, const UpdateQuery &b) {
        return a.x < b.x;
    });

    int ans = int(1e9) + 10;
    SegmentTree tree(M);
    for (int i = 0; i < stn; i++) {
        int x = q[i].x;

        while(i < stn && q[i].x == x) {
            tree.add(q[i].l, q[i].r, q[i].add);
            //cout << q[i].l << " " << q[i].r << " " << q[i].add << ":\n";
            i++;
        }
        i--;
        //cout << "::\n";

        ans = min(ans, tree.get());

        if (ans <= budget) {
            return ans;
        }
    }

    return ans;
}

void solve() {
    cin >> n >> m;

    cin >> budget;

    cin >> p;

    x.resize(p);
    y.resize(p);
    x2.resize(p);
    y2.resize(p);
    cost.resize(p);

    for (int i = 0; i < p; i++) {
        cin >> x[i] >> y[i] >> x2[i] >> y2[i] >> cost[i];
    }

    int l = 1, r = min(n, m) + 1;
    while(l < r) {
        int c = l + r >> 1;
        int res = getCost(c);
        if (res <= budget) {
            l = c + 1;
        }
        else {
            r = c;
        }
    }

    //cout << getCost(l - 1) << "\n";
    cout << l - 1 << "\n";
}


int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    //freopen("./input.txt", "r", stdin);

    solve();
}

Compilation message (stderr)

pyramid_base.cpp: In member function 'void SegmentTree::update(int, int, int, int, int, int)':
pyramid_base.cpp:58:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         int tm = tl + tr >> 1;
      |                  ~~~^~~~
pyramid_base.cpp: In function 'void solve()':
pyramid_base.cpp:139:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  139 |         int c = l + r >> 1;
      |                 ~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 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: 10 / 10
• Subtask 15: 0 / 10