Submission #532718

#	Time	Username	Problem	Language	Result	Execution time	Memory
532718		prvocislo	Pyramid Base (IOI08_pyramid_base)	C++17	25 / 100	5099 ms	112464 KiB

pyramid_base

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;

const int maxn = 1 << 20;
int l[maxn * 2], r[maxn * 2];
ll add[maxn * 2], mini[maxn * 2];
void update(int li, int ri, ll x, int vr)
{
    if (ri < l[vr] || r[vr] < li) return;
    if (li <= l[vr] && r[vr] <= ri)
    {
        add[vr] += x;
        mini[vr] += x;
        return;
    }
    update(li, ri, x, vr << 1);
    update(li, ri, x, (vr << 1) | 1);
    mini[vr] = min(mini[vr << 1], mini[(vr << 1) | 1]) + add[vr];
}
int X, Y, p;
ll b;
vector<int> ox1, oy1, ox2, oy2, c;
struct udalost
{
    int x1, x2, y;
    ll k;
};
bool cmp(udalost a, udalost b)
{
    return a.y < b.y;
}
bool check(int k)
{
    fill(add, add + maxn * 2, 0);
    fill(mini, mini + maxn * 2, 0);
    vector<udalost> v;
    v.push_back({ 0, k, 0, b + 1 });
    v.push_back({ X + 1, maxn, 0, b + 1 });
    for (int i = 0; i < p; i++)
    {
        v.push_back({ ox1[i], ox2[i] + k - 1, oy1[i], c[i] });
        v.push_back({ ox1[i], ox2[i] + k - 1, oy2[i] + k, -c[i] });
    }
    sort(v.begin(), v.end(), cmp);
    for (int i = 0; i < v.size(); i++)
    {
        update(v[i].x1, v[i].x2, v[i].k, 1);
        /*if (k == 5) for (int j = 0; j < maxn; j++)
        {
            int s = 0;
            for (int vr = j + maxn; vr > 0; vr >>= 1) s += add[vr];
            cout << s << " ";
        }
        cout << "\n";*/
        if (v[i].y <= k - 1 || v[i].y >= Y) continue;
        if ((i + 1 == v.size() || v[i].y < v[i + 1].y) && mini[1] <= b)
            return true;
    }
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    for (int i = maxn; i < maxn * 2; i++)
    {
        l[i] = i - maxn;
        r[i] = i - maxn;
    }
    for (int i = maxn - 1; i > 0; i--)
    {
        l[i] = l[i << 1];
        r[i] = r[(i << 1) | 1];
    }
    cin >> X >> Y >> b >> p;
    ox1.assign(p, 0);
    oy1.assign(p, 0);
    ox2.assign(p, 0);
    oy2.assign(p, 0);
    c.assign(p, 0);
    for (int i = 0; i < p; i++)
    {
        cin >> ox1[i] >> oy1[i] >> ox2[i] >> oy2[i] >> c[i];
    }
    int lo = 0, hi = min(X, Y);
    while (lo < hi)
    {
        int mi = (lo + hi + 1) / 2;
        if (check(mi)) lo = mi;
        else hi = mi - 1;
    }
    cout << lo << "\n";
    return 0;
}

Compilation message (stderr)

pyramid_base.cpp: In function 'bool check(int)':
pyramid_base.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<udalost>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~
pyramid_base.cpp:70:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<udalost>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         if ((i + 1 == v.size() || v[i].y < v[i + 1].y) && mini[1] <= b)
      |              ~~~~~~^~~~~~~~~~~

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