oj.uz

답안 #547730

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
547730 2022-04-11T14:35:34 Z alexxela12345 Pyramid Base (IOI08_pyramid_base) C++17
70 / 100
 5000 ms 53560 KB 
#pragma GCC optimize("Ofast,unroll-loops,fast-math,inline,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,avx,avx2,abm,mmx,popcnt")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ldb;

//#define int ll

const int INF = 2e9 + 228;

struct obstacle {
    int x1, y1, x2, y2, cost;
};

int n, m;
int p;
int q;
vector<obstacle> obstacles;

const int MAXN = 1e6 + 228;

int tree[4 * MAXN];
int mod[4 * MAXN];

void push(int v, int l, int r) {
    tree[v] += mod[v];
    if (l + 1 != r) {
        mod[2 * v + 1] += mod[v];
        mod[2 * v + 2] += mod[v];   
    }
    mod[v] = 0;
}

void add(int v, int l, int r, int ql, int qr, int val) {
    push(v, l, r);
    if (l >= qr || ql >= r) {
        return;
    }
    if (ql <= l && r <= qr) {
        mod[v] += val;
        push(v, l, r);
        return;
    }
    int m = (l + r) / 2;
    add(2 * v + 1, l, m, ql, qr, val);
    add(2 * v + 2, m, r, ql, qr, val);
    tree[v] = min(tree[2 * v + 1], tree[2 * v + 2]);
}

void add(int l, int r, int val) {
    add(0, 0, m, l, r, val);
}

int get(int v, int l, int r, int ql, int qr) {
    push(v, l, r);
    if (l >= qr || ql >= r) {
        return INF;
    }
    if (ql <= l && r <= qr) {
        return tree[v];
    }
    int m = (l + r) / 2;
    return min(get(2 * v + 1, l, m, ql, qr), get(2 * v + 2, m, r, ql, qr));
}

int get_mn(int l, int r) {
    return get(0, 0, m, l, r);
}

bool canBuild(int r) {
    vector<array<int, 4>> qq; // {time, l, r, val}
    for (int i = 0; i < q; i++) {
        qq.push_back({max(0, obstacles[i].x1 - r + 1), max(0, obstacles[i].y1 - r + 1), obstacles[i].y2, obstacles[i].cost});
        qq.push_back({obstacles[i].x2, max(0, obstacles[i].y1 - r + 1), obstacles[i].y2, -obstacles[i].cost});
    }
    qq.push_back({0, 0, m, 0});
    qq.push_back({n, 0, m, 0});
    sort(qq.begin(), qq.end());
    int last_time = 0;
    bool ans = 0;
    for (auto el : qq) {
        if (el[0] != last_time && last_time + r <= n) {
            int el = get_mn(0, m - r + 1);
            if (el <= p) {
                ans = 1;
            }
        }
        last_time = el[0];
        add(el[1], el[2], el[3]);
    }
    return ans;
}

void solve() {
    cin >> n >> m >> p >> q;
    obstacles.resize(q);
    for (int i = 0; i <q; i++) {
        cin >> obstacles[i].x1;
        cin >> obstacles[i].y1;
        cin >> obstacles[i].x2;
        cin >> obstacles[i].y2;
        cin >> obstacles[i].cost;
        obstacles[i].x1--;
        obstacles[i].y1--;
        if (p == 0) {
            obstacles[i].cost = 1;
        }
    }
    int L = 0;
    int R = min(n, m) + 1;
    while (R - L > 1) {
        int M = (L + R) / 2;
        if (canBuild(M)) {
            L = M;
        } else {
            R = M;
        }
    }
    cout << L << endl;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 340 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 664 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 2456 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 10736 KB Output is correct
2 Correct 53 ms 16440 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 16408 KB Output is correct
2 Correct 29 ms 11132 KB Output is correct

Subtask #8
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 1128 KB Output is correct
2 Correct 85 ms 1204 KB Output is correct
3 Correct 92 ms 1124 KB Output is correct

Subtask #9
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 374 ms 3672 KB Output is correct
2 Correct 429 ms 3728 KB Output is correct
3 Correct 394 ms 3656 KB Output is correct

Subtask #10
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 680 ms 18816 KB Output is correct
2 Correct 115 ms 2376 KB Output is correct
3 Correct 295 ms 18804 KB Output is correct
4 Correct 983 ms 18920 KB Output is correct

Subtask #11
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1025 ms 19228 KB Output is correct
2 Correct 1044 ms 19116 KB Output is correct
3 Correct 730 ms 19308 KB Output is correct

Subtask #12
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 995 ms 19440 KB Output is correct
2 Correct 1402 ms 19640 KB Output is correct
3 Correct 1361 ms 19408 KB Output is correct
4 Correct 1489 ms 19620 KB Output is correct
5 Correct 1324 ms 19484 KB Output is correct
6 Correct 756 ms 19448 KB Output is correct

Subtask #13
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5058 ms 35292 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5057 ms 48504 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5046 ms 53560 KB Time limit exceeded
2 Halted 0 ms 0 KB -