oj.uz

Submission #197911

# Submission time Handle Problem Language Result Execution time Memory
197911 2020-01-24T07:24:24 Z SamAnd Pyramid Base (IOI08_pyramid_base) C++17
100 / 100
 1891 ms 126476 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1000006;
struct ban
{
    int x1, y1, x2, y2, b;
};

int n, m, b;
int q;
ban a[N];

vector<int> va[N], vh[N];

int t[N * 4];
int laz[N * 4];

void shi(int pos)
{
    if (laz[pos] == 0)
        return;
    t[pos * 2] += laz[pos];
    t[pos * 2 + 1] += laz[pos];
    laz[pos * 2] += laz[pos];
    laz[pos * 2 + 1] += laz[pos];
    laz[pos] = 0;
}

void bil(int tl, int tr, int pos)
{
    t[pos] = 0;
    laz[pos] = 0;
    if (tl == tr)
    {
        return;
    }
    int m = (tl + tr) / 2;
    bil(tl, m, pos * 2);
    bil(m + 1, tr, pos * 2 + 1);
}

void ubd(int tl, int tr, int l, int r, int y, int pos)
{
    if (l > r)
        return;
    if (tl == l && tr == r)
    {
        t[pos] += y;
        laz[pos] += y;
        return;
    }
    shi(pos);
    int m = (tl + tr) / 2;
    ubd(tl, m, l, min(m, r), y, pos * 2);
    ubd(m + 1, tr, max(m + 1, l), r, y, pos * 2 + 1);
    t[pos] = min(t[pos * 2], t[pos * 2 + 1]);
}

bool stg(int u)
{
    bil(1, m - u + 1, 1);
    for (int i = 1; i <= u; ++i)
    {
        for (int j = 0; j < va[i].size(); ++j)
        {
            int k = va[i][j];
            ubd(1, m - u + 1, max(a[k].y1 - u + 1, 1), min(a[k].y2, m - u + 1), a[k].b, 1);
        }
    }
    if (t[1] <= b)
        return true;
    for (int i = 2; i <= n - u + 1; ++i)
    {
        for (int j = 0; j < va[i + u - 1].size(); ++j)
        {
            int k = va[i + u - 1][j];
            ubd(1, m - u + 1, max(a[k].y1 - u + 1, 1), min(a[k].y2, m - u + 1), a[k].b, 1);
        }
        for (int j = 0; j < vh[i - 1].size(); ++j)
        {
            int k = vh[i - 1][j];
            ubd(1, m - u + 1, max(a[k].y1 - u + 1, 1), min(a[k].y2, m - u + 1), -a[k].b, 1);
        }
        if (t[1] <= b)
            return true;
    }
    return false;
}

void solv1()
{
    int l = 1, r = min(n, m);
    int ans = 0;
    while (l <= r)
    {
        int m = (l + r) / 2;
        if (stg(m))
        {
            ans = m;
            l = m + 1;
        }
        else
            r = m - 1;
    }
    printf("%d\n", ans);
}

struct ban1
{
    int l, r, ans, e;
    ban1(){}
    ban1(int x, int e)
    {
        l = r = ans = x;
        this->e = e;
    }
};

int q1[N * 4];
ban1 t1[N * 4];

void bil1(int tl, int tr, int pos)
{
    t1[pos] = ban1(tr - tl + 1, tr - tl + 1);
    if (tl == tr)
        return;
    int m = (tl + tr) / 2;
    bil1(tl, m, pos * 2);
    bil1(m + 1, tr, pos * 2 + 1);
}

ban1 mer1(const ban1& l, const ban1& r)
{
    ban1 res;
    res.e = l.e + r.e;
    if (l.l == l.e)
        res.l = l.l + r.l;
    else
        res.l = l.l;
    if (r.r == r.e)
        res.r = r.r + l.r;
    else
        res.r = r.r;
    res.ans = max(l.ans, r.ans);
    res.ans = max(res.ans, l.r + r.l);
    return res;
}

void ubd1(int tl, int tr, int l, int r, int y, int pos)
{
    if (l > r)
        return;
    if (tl == l && tr == r)
    {
        q1[pos] += y;
        if (!q1[pos])
        {
            if (tl == tr)
                t1[pos] = ban1(1, 1);
            else
                t1[pos] = mer1(t1[pos * 2], t1[pos * 2 + 1]);
        }
        else
            t1[pos] = ban1(0, (r - l + 1));
        return;
    }
    int m = (tl + tr) / 2;
    ubd1(tl, m, l, min(m, r), y, pos * 2);
    ubd1(m + 1, tr, max(m + 1, l), r, y, pos * 2 + 1);
    if (!q1[pos])
        t1[pos] = mer1(t1[pos * 2], t1[pos * 2 + 1]);
    else
        t1[pos] = ban1(0, (tr - tl + 1));
}

void solv2()
{
    int ans = 0;
    bil1(1, m, 1);
    int r = 0;
    for (int l = 1; l <= m; ++l)
    {
        while (1)
        {
            if (r == n + 1)
                break;
            if (t1[1].ans < (r - l + 1))
                break;
            ++r;
            for (int j = 0; j < va[r].size(); ++j)
            {
                int k = va[r][j];
                ubd1(1, m, a[k].y1, a[k].y2, 1, 1);
            }
        }
        ans = max(ans, r - l);
        for (int j = 0; j < vh[l].size(); ++j)
        {
            int k = vh[l][j];
            ubd1(1, m, a[k].y1, a[k].y2, -1, 1);
        }
    }
    printf("%d\n", ans);
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    #endif // SOMETHING
    scanf("%d%d", &n, &m);
    scanf("%d", &b);
    scanf("%d", &q);
    for (int i = 1; i <= q; ++i)
        scanf("%d%d%d%d%d", &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2, &a[i].b);
    for (int i = 1; i <= q; ++i)
    {
        va[a[i].x1].push_back(i);
        vh[a[i].x2].push_back(i);
    }
    if (b > 0)
    {
        solv1();
        return 0;
    }
    solv2();
    return 0;
}

Compilation message

pyramid_base.cpp: In function 'bool stg(int)':
pyramid_base.cpp:64:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < va[i].size(); ++j)
                         ~~^~~~~~~~~~~~~~
pyramid_base.cpp:74:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < va[i + u - 1].size(); ++j)
                         ~~^~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp:79:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < vh[i - 1].size(); ++j)
                         ~~^~~~~~~~~~~~~~~~~~
pyramid_base.cpp: In function 'void solv2()':
pyramid_base.cpp:190:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < va[r].size(); ++j)
                             ~~^~~~~~~~~~~~~~
pyramid_base.cpp:197:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < vh[l].size(); ++j)
                         ~~^~~~~~~~~~~~~~
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:211:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
pyramid_base.cpp:212:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &b);
     ~~~~~^~~~~~~~~~
pyramid_base.cpp:213:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
pyramid_base.cpp:215:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d%d", &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2, &a[i].b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 47384 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 47996 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 52472 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 84972 KB Output is correct
2 Correct 101 ms 85628 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 82952 KB Output is correct
2 Correct 101 ms 85036 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 47948 KB Output is correct
2 Correct 99 ms 48116 KB Output is correct
3 Correct 88 ms 47920 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 50952 KB Output is correct
2 Correct 392 ms 51036 KB Output is correct
3 Correct 330 ms 50936 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 57768 KB Output is correct
2 Correct 75 ms 49312 KB Output is correct
3 Correct 268 ms 64916 KB Output is correct
4 Correct 672 ms 66016 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 672 ms 66548 KB Output is correct
2 Correct 1194 ms 66296 KB Output is correct
3 Correct 279 ms 58456 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 495 ms 58972 KB Output is correct
2 Correct 1599 ms 66936 KB Output is correct
3 Correct 1443 ms 66984 KB Output is correct
4 Correct 1565 ms 66904 KB Output is correct
5 Correct 1534 ms 66812 KB Output is correct
6 Correct 219 ms 58868 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 875 ms 109372 KB Output is correct
2 Correct 302 ms 67064 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1126 ms 118624 KB Output is correct
2 Correct 1259 ms 114672 KB Output is correct
3 Correct 817 ms 106292 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1384 ms 126476 KB Output is correct
2 Correct 1856 ms 125476 KB Output is correct
3 Correct 1891 ms 125332 KB Output is correct
4 Correct 1652 ms 123084 KB Output is correct
5 Correct 1123 ms 117552 KB Output is correct