oj.uz

Submission #239232

# Submission time Handle Problem Language Result Execution time Memory
239232 2020-06-14T21:21:03 Z osaaateiasavtnl Pyramid Base (IOI08_pyramid_base) C++14
100 / 100
 1343 ms 141944 KB 
#include <bits/stdc++.h>

using namespace std;
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC

const int N = 1e6 + 7, P = 30001;
struct Rect {
    int x1, y1, x2, y2, c;
} a[P];
int p;

struct Event {
    int x, l, r, c;
    bool operator < (Event e) {
        return x < e.x;
    }   
};  

struct Tree {
  
int n;
int tree[N << 2], prop[N << 2];

void init(int n_) {
    n = n_;
    memset(tree, 0, sizeof tree);
    memset(prop, 0, sizeof prop);
}

int get() {
    return tree[0];
}

void gap(int v, int x) {
    prop[v] += x;
    tree[v] += x;
}   
void push(int v) {
    gap(v * 2 + 1, prop[v]);
    gap(v * 2 + 2, prop[v]);
    prop[v] = 0;
}   
void relax(int v) {
    tree[v] = min(tree[v * 2 + 1], tree[v * 2 + 2]);
}   
void add(int v, int tl, int tr, int l, int r, int x) {
    if (tr < l || r < tl)
        return;
    if (l <= tl && tr <= r) {
        gap(v, x);
        return;
    }   
    int tm = (tl + tr) >> 1;
    push(v);
    add(v * 2 + 1, tl, tm, l, r, x);
    add(v * 2 + 2, tm + 1, tr, l, r, x);
    relax(v);

    //cout << tl << ' ' << tr << " : " << tree[v] << endl;
}   

void add(int l, int r, int x) {
    add(0, 1, n, l, r, x);
}   

} mag;

const int INF = 2e9 + 7;
bool check(int n, int m, int b, int mid) {
    if (mid > m)
        return 0;

    vector <Event> s;
    for (int i = 0; i < p; ++i) {
        int x1 = max(1, a[i].x1 - mid + 1);
        int y1 = max(1, a[i].y1 - mid + 1);
        s.app({x1, y1, a[i].y2, a[i].c});
        s.app({a[i].x2 + 1, y1, a[i].y2, -a[i].c});
    }   

    mag.init(m - mid + 1);

    sort(all(s));
    int cost = INF;
    for (int i = 0; i < s.size(); ++i) {
        auto e = s[i];
        if (e.x + mid - 1 > n)
            break;

        mag.add(s[i].l, s[i].r, s[i].c);

        //cout << m - mid + 1 << endl;
        //cout << "add " << s[i].x << ' ' << s[i].l << ' ' << s[i].r << ' ' << s[i].c << endl;

        if (i + 1 < s.size() && s[i+1].x == s[i].x)
            continue;
        cost = min(cost, mag.get());                            
    }
    return cost <= b;
}   

void LMAO_ROFL_2020(int n, int m, int b) {
    swap(n, m);

    cin >> p;
    for (int i = 0; i < p; ++i) {
        cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2 >> a[i].c;
    }   
    
    int l = 0, r = N;
    while (l < r - 1) {
        int mid = (l + r) >> 1;
        if (check(n, m, b, mid))
            l = mid;
        else
            r = mid;
    }   
    cout << l << endl;
    exit(0);
}

namespace LMAO {
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() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

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

    int b;
    cin >> b;
    if (b != 0) {
        LMAO_ROFL_2020(n, m, b);
    }   

    using namespace LMAO;

    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

pyramid_base.cpp: In function 'bool check(int, int, int, int)':
pyramid_base.cpp:93:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < s.size(); ++i) {
                     ~~^~~~~~~~~~
pyramid_base.cpp:103:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i + 1 < s.size() && s[i+1].x == s[i].x)
             ~~~~~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47480 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 48376 KB Output is correct

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 113020 KB Output is correct
2 Correct 97 ms 113144 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 113144 KB Output is correct
2 Correct 96 ms 113064 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 79356 KB Output is correct
2 Correct 166 ms 79292 KB Output is correct
3 Correct 142 ms 79288 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 80384 KB Output is correct
2 Correct 408 ms 80416 KB Output is correct
3 Correct 332 ms 80384 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 81472 KB Output is correct
2 Correct 86 ms 81164 KB Output is correct
3 Correct 257 ms 81260 KB Output is correct
4 Correct 682 ms 81440 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 531 ms 81796 KB Output is correct
2 Correct 801 ms 81896 KB Output is correct
3 Correct 257 ms 81960 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 82116 KB Output is correct
2 Correct 1106 ms 82184 KB Output is correct
3 Correct 1047 ms 82300 KB Output is correct
4 Correct 1022 ms 82228 KB Output is correct
5 Correct 1020 ms 82368 KB Output is correct
6 Correct 234 ms 82200 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 757 ms 129656 KB Output is correct
2 Correct 404 ms 67068 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 932 ms 136316 KB Output is correct
2 Correct 1006 ms 133152 KB Output is correct
3 Correct 626 ms 126152 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1172 ms 141944 KB Output is correct
2 Correct 1343 ms 139752 KB Output is correct
3 Correct 1321 ms 139784 KB Output is correct
4 Correct 1255 ms 137968 KB Output is correct
5 Correct 830 ms 132312 KB Output is correct