oj.uz

답안 #239220

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
239220 2020-06-14T20:45:21 Z osaaateiasavtnl Pyramid Base (IOI08_pyramid_base) C++14
65 / 100
 1397 ms 151932 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 7;
const int INF = 1e9 + 7;

struct Point {
    int x, y;
};

struct Node {
    int len, mn, l, r, val, lval, rval, add;
};

Node tree[MAXN * 4];

void calc(int v) {
    tree[v].len = tree[v * 2 + 1].len + tree[v * 2 + 2].len;
    tree[v].mn = min(tree[v * 2 + 1].mn, tree[v * 2 + 2].mn);
    tree[v].lval = tree[v * 2 + 1].lval;
    tree[v].rval = tree[v * 2 + 2].rval;

    if (tree[v * 2 + 1].l == tree[v * 2 + 1].len && tree[v * 2 + 1].lval == tree[v * 2 + 2].lval) {
        tree[v].l = tree[v * 2 + 1].len + tree[v * 2 + 2].l;
    }
    else {
        tree[v].l = tree[v * 2 + 1].l;
    }

    if (tree[v * 2 + 2].r == tree[v * 2 + 2].len && tree[v * 2 + 1].rval == tree[v * 2 + 2].rval) {
        tree[v].r = tree[v * 2 + 2].len + tree[v * 2 + 1].r;
    }
    else {
        tree[v].r = tree[v * 2 + 2].r;
    }

    tree[v].val = -INF;
    if (tree[v * 2 + 1].mn == tree[v].mn) tree[v].val = max(tree[v].val, tree[v * 2 + 1].val);
    if (tree[v * 2 + 2].mn == tree[v].mn) tree[v].val = max(tree[v].val, tree[v * 2 + 2].val);
    if (tree[v * 2 + 1].rval == tree[v].mn && tree[v * 2 + 2].lval == tree[v].mn) {
        tree[v].val = max(tree[v].val, tree[v * 2 + 1].r + tree[v * 2 + 2].l);
    }
}

void push(int v) {
    tree[v * 2 + 1].add += tree[v].add;
    tree[v * 2 + 1].mn += tree[v].add;
    tree[v * 2 + 1].lval += tree[v].add;
    tree[v * 2 + 1].rval += tree[v].add;

    tree[v * 2 + 2].add += tree[v].add;
    tree[v * 2 + 2].mn += tree[v].add;
    tree[v * 2 + 2].lval += tree[v].add;
    tree[v * 2 + 2].rval += tree[v].add;

    tree[v].add = 0;
}

void upd(int v, int tl, int tr, int l, int r, int x) {
    if (tr < l || r < tl) return;
    if (l <= tl && tr <= r) {
        tree[v].add += x;
        tree[v].lval += x;
        tree[v].rval += x;
        tree[v].mn += x;
        return;
    }

    int tm = (tl + tr) / 2;
    push(v);
    upd(v * 2 + 1, tl, tm, l, r, x);
    upd(v * 2 + 2, tm + 1, tr, l, r, x);
    calc(v);
}

vector <pair <int, int> > add_sc[MAXN];
vector <pair <int, int> > del_sc[MAXN];

bool check(int lx, int rx) {
    return (tree[0].mn == 0 && tree[0].val >= rx - lx + 1);
}

void build(int v, int tl, int tr) {
    if (tl == tr) {
        tree[v].len = 1;
        tree[v].mn = 0;
        tree[v].l = 1;
        tree[v].r = 1;
        tree[v].val = 1;
        tree[v].lval = 0;
        tree[v].rval = 0;
        tree[v].add = 0;
        return;
    }

    int tm = (tl + tr) / 2;
    build(v * 2 + 1, tl, tm);
    build(v * 2 + 2, tm + 1, tr);
    calc(v);
}

void myadd(int r, int n) {
    for (pair <int, int> e : add_sc[r]) {
        upd(0, 1, n, e.first, e.second, 1);
    }
}

void mydel(int l, int n) {
    for (pair <int, int> e : del_sc[l]) {
        upd(0, 1, n, e.first, e.second, -1);
    }
}

signed main() {
    ios_base::sync_with_stdio(false);

    int m, n;
    cin >> m >> n;

    int b;
    cin >> b;
    if (b != 0) return 1;

    int p;
    cin >> p;
    vector <pair <Point, Point> > a(p);
    for (int i = 0; i < p; ++i) {
        cin >> a[i].first.x >> a[i].first.y >> a[i].second.x >> a[i].second.y;
        int c;
        cin >> c;
    }

    for (int i = 0; i < p; ++i) {
        add_sc[a[i].first.x].push_back({a[i].first.y, a[i].second.y});
        del_sc[a[i].second.x + 1].push_back({a[i].first.y, a[i].second.y});
    }

    build(0, 1, n);

    int ans = 0;
    int rx = 1;
    myadd(1, n);
    for (int lx = 1; lx <= m; ++lx) {
        if (rx < lx) {
            for (int i = rx + 1; i <= lx; ++i) myadd(i, n);
            rx = lx;
        }

        mydel(lx, n);

        while (rx <= m && check(lx, rx)) {
            ++rx;
            myadd(rx, n);
        }

        ans = max(ans, rx - lx);
    }

    cout << ans << '\n';

    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 113120 KB Output is correct
2 Correct 95 ms 113144 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 113016 KB Output is correct
2 Correct 89 ms 113212 KB Output is correct

Subtask #8
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 30 ms 47360 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 36 ms 47360 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 33 ms 47360 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 30 ms 47360 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 33 ms 47352 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #13
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 706 ms 133400 KB Output is correct
2 Correct 384 ms 70136 KB Output is correct

Subtask #14
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 916 ms 142972 KB Output is correct
2 Correct 904 ms 139100 KB Output is correct
3 Correct 576 ms 131912 KB Output is correct

Subtask #15
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1213 ms 151932 KB Output is correct
2 Correct 1387 ms 149236 KB Output is correct
3 Correct 1397 ms 149280 KB Output is correct
4 Correct 1210 ms 147168 KB Output is correct
5 Correct 861 ms 141968 KB Output is correct