oj.uz

Submission #532718

# Submission time Handle Problem Language Result Execution time Memory
532718 2022-03-03T17:18:56 Z prvocislo Pyramid Base (IOI08_pyramid_base) C++17
25 / 100
 5000 ms 112464 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, 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

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.0 / 5.0

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

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 49492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 49720 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 49612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 49684 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 49680 KB Output is correct
2 Correct 151 ms 49732 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 49592 KB Output is correct
2 Correct 137 ms 49688 KB Output is correct

Subtask #8
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 50368 KB Output is correct
2 Incorrect 129 ms 50424 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 51640 KB Output is correct
2 Incorrect 522 ms 51764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 637 ms 53004 KB Output is correct
2 Incorrect 276 ms 52844 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 951 ms 53476 KB Output is correct
2 Correct 1296 ms 53608 KB Output is correct
3 Incorrect 759 ms 53536 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1081 ms 54260 KB Output is correct
2 Incorrect 1657 ms 54188 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5014 ms 81080 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 5099 ms 102924 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 5089 ms 112464 KB Time limit exceeded
2 Halted 0 ms 0 KB -