Submission #1002477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002477		theboatman	Pyramid Base (IOI08_pyramid_base)	C++17	5 / 100	683 ms	118100 KiB

pyramid_base

#include <bits/stdc++.h>
 
using namespace std;

const int N = int(1e6) + 10;

int n, m, p;
int budget;
vector <int> x, y, x2, y2, cost;
 
struct Node {
    int pref, suff, mx;
};

Node t[N * 4];
int lazy[N * 4]; 
struct SegmentTree {
    int v;
    int tl;
    int tr;
 
    SegmentTree(int n) {
      
        v = 1;
        tl = 1;
        tr = n;

        build(v, tl, tr);
    };
 
    void add(int l, int r, int incVal) {
        update(v, tl, tr, l, r, incVal);
    }
 
    int get() {
        return t[v].mx;
    }
 
    private:
    void update(int v, int tl, int tr, int l, int r, int incVal) { 
        if (l > r) {
            return;
        }
 
        if (tl == l && tr == r) {
            lazy[v] += incVal;
            combine(v, tl, tr);
            return;
        }

        int tm = tl + tr >> 1;
        update(v << 1, tl, tm, l, min(r, tm), incVal);
        update(v << 1 | 1, tm + 1, tr, max(tm + 1, l), r, incVal);
 
        combine(v, tl, tr);
    }

    void build(int v, int tl, int tr) {
        if (tl == tr) {
            combine(v, tl, tr);
            return;
        }

        int tm = tl + tr >> 1;
        build(v << 1, tl, tm);
        build(v << 1 | 1, tm + 1, tr);

        combine(v, tl, tr);
    }

    void combine(int v, int tl, int tr) {
        if (lazy[v]) {
            t[v].mx = 0;
            t[v].pref = 0;
            t[v].suff = 0;
            return;
        }

        if (tl == tr) {
            t[v].mx = 1;
            t[v].pref = 1;
            t[v].suff = 1;
            return;
        }

        int l = v << 1;
        int r = v << 1 | 1;

        
        int tm = tl + tr >> 1;
        int szLeft = tm - tl + 1;
        int szRight = tr - tm;

        t[v].mx = max(t[l].mx, t[r].mx);

        if (t[l].pref == szLeft) {
            t[v].pref = t[l].pref + t[r].pref;
        }
        else {
            t[v].pref = t[l].pref;
        }

        if (t[r].suff == szRight) {
            t[v].suff = t[l].suff + t[r].suff;
        }
        else {
            t[v].suff = t[r].suff;
        }

        t[v].mx = max(t[v].mx, t[v].pref);
        t[v].mx = max(t[v].mx, t[v].suff);
    }
};

vector <int> add[N];
vector <int> del[N];
 
void solve() {
    cin >> n >> m;
 
    cin >> budget;
 
    cin >> p;
 
    x.resize(p);
    y.resize(p);
    x2.resize(p);
    y2.resize(p);
    cost.resize(p);
 
    for (int i = 0; i < p; i++) {
        cin >> x[i] >> y[i] >> x2[i] >> y2[i] >> cost[i];
    }
 
    for (int i = 0; i < p; i++) {
        add[x[i]].push_back(i);
        del[x2[i] + 1].push_back(i);
    }

    SegmentTree tree(m + 1);
    for (auto i : add[1]) {
        tree.add(y[i], y2[i], 1);
    }

    int r = 1;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (auto i : del[i]) {
            tree.add(y[i], y2[i], -1);
        }

        while (r <= n && tree.get() >= r - i + 1) {
            ans = max(ans, r - i + 1);
            r++;
            for (auto i : add[r]) {
                tree.add(y[i], y2[i], 1);
            }
        }
    }

    cout << ans << "\n";
}
 
 
int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    //freopen("./input.txt", "r", stdin);
 
    solve();
}

Compilation message (stderr)

pyramid_base.cpp: In member function 'void SegmentTree::update(int, int, int, int, int, int)':
pyramid_base.cpp:51:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |         int tm = tl + tr >> 1;
      |                  ~~~^~~~
pyramid_base.cpp: In member function 'void SegmentTree::build(int, int, int)':
pyramid_base.cpp:64:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |         int tm = tl + tr >> 1;
      |                  ~~~^~~~
pyramid_base.cpp: In member function 'void SegmentTree::combine(int, int, int)':
pyramid_base.cpp:90:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |         int tm = tl + tr >> 1;
      |                  ~~~^~~~

• Subtask 1: 0 / 5
• Subtask 2: 5 / 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