oj.uz

Submission #532719

# Submission time Handle Problem Language Result Execution time Memory
532719 2022-03-03T17:47:06 Z prvocislo Pyramid Base (IOI08_pyramid_base) C++17
70 / 100
 5000 ms 100812 KB 
#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 - 1, 0, b + 1 });
    v.push_back({ X + 1, maxn, 0, b + 1 });
    v.push_back({ 0, 0, Y, 0 });
    v.push_back({ 0, 0, k, 0 });
    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 (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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 49484 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 49540 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 49496 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 49612 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 49612 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 49664 KB Output is correct
2 Correct 125 ms 49612 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 49664 KB Output is correct
2 Correct 114 ms 49632 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 50260 KB Output is correct
2 Correct 124 ms 50272 KB Output is correct
3 Correct 146 ms 50440 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 51408 KB Output is correct
2 Correct 467 ms 51304 KB Output is correct
3 Correct 445 ms 51692 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 52552 KB Output is correct
2 Correct 232 ms 52400 KB Output is correct
3 Correct 123 ms 52936 KB Output is correct
4 Correct 948 ms 53132 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 868 ms 52844 KB Output is correct
2 Correct 1229 ms 52916 KB Output is correct
3 Correct 731 ms 52916 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 998 ms 53212 KB Output is correct
2 Correct 1605 ms 53260 KB Output is correct
3 Correct 1440 ms 54168 KB Output is correct
4 Correct 1655 ms 54216 KB Output is correct
5 Correct 1447 ms 54108 KB Output is correct
6 Correct 778 ms 54240 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5064 ms 75296 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5063 ms 94356 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5065 ms 100812 KB Time limit exceeded
2 Halted 0 ms 0 KB -