oj.uz

Submission #1000606

# Submission time Handle Problem Language Result Execution time Memory
1000606 2024-06-18T00:30:54 Z theboatman Pyramid Base (IOI08_pyramid_base) C++17
90 / 100
 5000 ms 65480 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1108 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3680 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15964 KB Output is correct
2 Correct 86 ms 32072 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 29932 KB Output is correct
2 Correct 13 ms 15964 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 856 KB Output is correct
2 Correct 36 ms 1232 KB Output is correct
3 Correct 34 ms 1272 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 5692 KB Output is correct
2 Correct 206 ms 6496 KB Output is correct
3 Correct 165 ms 6632 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 19292 KB Output is correct
2 Correct 19 ms 3420 KB Output is correct
3 Correct 108 ms 34840 KB Output is correct
4 Correct 219 ms 32944 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 27196 KB Output is correct
2 Correct 538 ms 35160 KB Output is correct
3 Correct 53 ms 19548 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 19804 KB Output is correct
2 Correct 622 ms 35416 KB Output is correct
3 Correct 623 ms 35536 KB Output is correct
4 Correct 704 ms 35528 KB Output is correct
5 Correct 675 ms 35540 KB Output is correct
6 Correct 31 ms 19840 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3129 ms 47572 KB Output is correct
2 Correct 615 ms 17696 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4505 ms 56504 KB Output is correct
2 Correct 3857 ms 56232 KB Output is correct
3 Correct 1998 ms 50228 KB Output is correct

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5056 ms 65480 KB Time limit exceeded
2 Halted 0 ms 0 KB -