Submission #239219

#	Time	Username	Problem	Language	Result	Execution time	Memory
239219		osaaateiasavtnl	Pyramid Base (IOI08_pyramid_base)	C++17	0 / 100	43 ms	47396 KiB

pyramid_base

#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);
    freopen("input.txt", "r", stdin);

    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;
}

Compilation message (stderr)

pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:117:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("input.txt", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 7
• Subtask 9: 0 / 7
• Subtask 10: 0 / 7
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10