oj.uz

Submission #503856

# Submission time Handle Problem Language Result Execution time Memory
503856 2022-01-09T05:00:43 Z tabr Pyramid Base (IOI08_pyramid_base) C++17
70 / 100
 5000 ms 77712 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

long long e() {
    return (long long) 1e18;
}

long long id() {
    return 0;
}

long long op(long long a, long long b) {
    return min(a, b);
}

long long mapping(long long f, long long x) {
    return f + x;
}

long long composition(long long f, long long g) {
    return f + g;
}

const int SEG_N = 1 << 19;
long long node[2 * SEG_N];
long long lazy[SEG_N];

void build(int sz) {
    for (int i = 0; i < 2 * SEG_N; i++) {
        node[i] = e();
    }
    for (int i = 0; i < SEG_N; i++) {
        lazy[i] = id();
    }
    for (int i = 0; i < sz; i++) {
        node[i + SEG_N] = 0;
    }
    for (int i = SEG_N - 1; i > 0; i--) {
        node[i] = op(node[i * 2], node[i * 2 + 1]);
    }
}

void eval(int k) {
    node[2 * k] = mapping(lazy[k], node[2 * k]);
    node[2 * k + 1] = mapping(lazy[k], node[2 * k + 1]);
    if (2 * k < SEG_N) {
        lazy[2 * k] = composition(lazy[k], lazy[2 * k]);
        lazy[2 * k + 1] = composition(lazy[k], lazy[2 * k + 1]);
    }
    lazy[k] = id();
}

void update(int x, int y, long long v, int k = 1, int l = 0, int r = SEG_N) {
    if (y <= l || r <= x) {
        return;
    }
    if (x <= l && r <= y) {
        node[k] = mapping(v, node[k]);
        if (k < SEG_N) {
            lazy[k] = composition(v, lazy[k]);
        }
    } else {
        eval(k);
        update(x, y, v, 2 * k, l, (l + r) / 2);
        update(x, y, v, 2 * k + 1, (l + r) / 2, r);
        node[k] = op(node[2 * k], node[2 * k + 1]);
    }
}

long long get(int x, int y, int k = 1, int l = 0, int r = SEG_N) {
    if (y <= l || r <= x) {
        return e();
    }
    if (x <= l && r <= y) {
        return node[k];
    }
    eval(k);
    long long vl = get(x, y, 2 * k, l, (l + r) / 2);
    long long vr = get(x, y, 2 * k + 1, (l + r) / 2, r);
    return op(vl, vr);
}

const int N = (int) 1e6 + 10;
const int P = (int) 4e5 + 10;
tuple<int, int, int, int> a[P];
tuple<int, int, int, int> b[P];
int mp[N];
int xs[2 * P];
int ys[4 * P];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int h, w;
    cin >> h >> w;
    int d;
    cin >> d;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        x1--, y1--;
        a[i] = make_tuple(x1, y1, y2, c);
        b[i] = make_tuple(x2, y1, y2, c);
    }
    sort(a, a + n);
    sort(b, b + n);
    int hi = min(w, h) + 1;
    int lo = 0;
    while (hi - lo > 1) {
        int mid = (hi + lo) / 2;
        int aid = 0;
        int bid = 0;
        int ok = 0;
        for (int i = 0; i < n; i++) {
            auto [x2, y1, y2, c] = b[i];
            y1 = max(0, y1 - mid + 1);
            y2 = min(w - mid + 1, y2);
            ys[2 * i] = y1;
            ys[2 * i + 1] = y2;
            xs[i] = min(h - mid, x2);
        }
        for (int i = 0; i < n; i++) {
            auto [x1, y1, y2, c] = a[i];
            y1 = max(0, y1 - mid + 1);
            y2 = min(w - mid + 1, y2);
            ys[2 * n + 2 * i] = y1;
            ys[2 * n + 2 * i + 1] = y2;
            xs[i + n] = max(0, x1 - mid + 1);
        }
        xs[2 * n] = 0;
        xs[2 * n + 1] = h - mid;
        sort(xs, xs + 2 * n + 2);
        int xsz = (int) (unique(xs, xs + 2 * n + 2) - xs);
        ys[4 * n] = 0;
        ys[4 * n + 1] = w - mid + 1;
        sort(ys, ys + 4 * n + 2);
        int ysz = (int) (unique(ys, ys + 4 * n + 2) - ys);
        for (int i = 0; i < ysz; i++) {
            mp[ys[i]] = i;
        }
        build(ysz - 1);
        for (int xid = 0; xid < xsz; xid++) {
            int i = xs[xid];
            while (bid < n && get<0>(b[bid]) <= i) {
                auto [x2, y1, y2, c] = b[bid];
                y1 = max(0, y1 - mid + 1);
                y2 = min(w - mid + 1, y2);
                y1 = mp[y1];
                y2 = mp[y2];
                update(y1, y2, -c);
                bid++;
            }
            while (aid < n && get<0>(a[aid]) - mid + 1 <= i) {
                auto [x1, y1, y2, c] = a[aid];
                y1 = max(0, y1 - mid + 1);
                y2 = min(w - mid + 1, y2);
                y1 = mp[y1];
                y2 = mp[y2];
                update(y1, y2, c);
                aid++;
            }
            if (node[1] <= d) {
                ok = 1;
                break;
            }
        }
        if (ok) {
            lo = mid;
        } else {
            hi = mid;
        }
    }
    cout << lo << '\n';
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12620 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 12704 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 12748 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 13092 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 14140 KB Output is correct
2 Correct 62 ms 16492 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 16396 KB Output is correct
2 Correct 51 ms 14292 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 13048 KB Output is correct
2 Correct 85 ms 13072 KB Output is correct
3 Correct 103 ms 13056 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 14020 KB Output is correct
2 Correct 338 ms 14164 KB Output is correct
3 Correct 303 ms 13932 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 15960 KB Output is correct
2 Correct 64 ms 14108 KB Output is correct
3 Correct 135 ms 18008 KB Output is correct
4 Correct 344 ms 17784 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 17208 KB Output is correct
2 Correct 583 ms 18332 KB Output is correct
3 Correct 222 ms 16292 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 16432 KB Output is correct
2 Correct 728 ms 18544 KB Output is correct
3 Correct 708 ms 18456 KB Output is correct
4 Correct 743 ms 18372 KB Output is correct
5 Correct 790 ms 18456 KB Output is correct
6 Correct 236 ms 16512 KB Output is correct

Subtask #13
0 / 10.0

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

Subtask #14
0 / 10.0

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

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3062 ms 77712 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -