oj.uz

Submission #220717

# Submission time Handle Problem Language Result Execution time Memory
220717 2020-04-08T12:54:50 Z dolphingarlic Pyramid Base (IOI08_pyramid_base) C++14
65 / 100
 1350 ms 118120 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;

namespace no_remove {

struct Node {
    int sm, range, mxl, mxr, mxt;
};

Node segtree[4000001];
vector<pair<int, int>> add[1000002], subtr[1000002];

void combine(int node, Node l, Node r) {
    if (l.sm) l.mxl = l.mxr = l.mxt = 0;
    if (r.sm) r.mxl = r.mxr = r.mxt = 0;
    segtree[node] = {segtree[node].sm, l.range + r.range,
                     l.mxl + (l.mxl == l.range ? r.mxl : 0),
                     r.mxr + (r.mxl == r.range ? l.mxr : 0),
                     max({l.mxt, r.mxt, l.mxr + r.mxl})};
}

void build(int node, int l, int r) {
    if (l == r) segtree[node] = {0, 1, 1, 1, 1};
    else {
        int mid = (l + r) / 2;
        build(node * 2, l, mid);
        build(node * 2 + 1, mid + 1, r);
        combine(node, segtree[node * 2], segtree[node * 2 + 1]);
    }
}

void update(int a, int b, int val, int node, int l, int r) {
    if (l > b || r < a) return;
    if (l >= a && r <= b) segtree[node].sm += val;
    else {
        int mid = (l + r) / 2;
        update(a, b, val, node * 2, l, mid);
        update(a, b, val, node * 2 + 1, mid + 1, r);
        combine(node, segtree[node * 2], segtree[node * 2 + 1]);
    }
}

void solve(int H, int W) {
    add[H + 1].push_back({1, W});
    int N, C;
    cin >> N;
    FOR(i, 0, N) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2 >> C;
        add[x1].push_back({y1, y2});
        subtr[x2 + 1].push_back({y1, y2});
    }
    build(1, 1, W);

    int ans = 0, rptr = 1;
    FOR(lptr, 1, H + 1) {
        for (pair<int, int> i : subtr[lptr]) update(i.first, i.second, -1, 1, 1, W);
        while ((segtree[1].sm ? 0 : segtree[1].mxt) >= rptr - lptr) {
            for (pair<int, int> i : add[rptr]) update(i.first, i.second, 1, 1, 1, W);
            ans = max(ans, rptr++ - lptr);
        }
    }
    cout << ans;
}
}  // namespace no_remove

namespace yes_remove {
void solve(int H, int W, int B) { cout << 4; }
}  // namespace yes_remove

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int H, W, B;
    cin >> H >> W >> B;
    if (B) yes_remove::solve(H, W, B);
    else no_remove::solve(H, W);
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 47360 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47352 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47352 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 48000 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 52472 KB Output is correct

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 88440 KB Output is correct
2 Correct 83 ms 88416 KB Output is correct

Subtask #8
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 47352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 47360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 47308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 47360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 47352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 105644 KB Output is correct
2 Correct 401 ms 63992 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 922 ms 110968 KB Output is correct
2 Correct 969 ms 107624 KB Output is correct
3 Correct 555 ms 102596 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1139 ms 113912 KB Output is correct
2 Correct 1324 ms 111976 KB Output is correct
3 Correct 1350 ms 118120 KB Output is correct
4 Correct 1177 ms 116192 KB Output is correct
5 Correct 838 ms 110928 KB Output is correct