oj.uz

Submission #52762

# Submission time Handle Problem Language Result Execution time Memory
52762 2018-06-26T16:58:07 Z SpaimaCarpatilor Pyramid Base (IOI08_pyramid_base) C++17
65 / 100
 2359 ms 138552 KB 
#include<bits/stdc++.h>

using namespace std;

int budget, N, M, K;
const int maxX = 1000000;

int mi[4 * maxX + 100], b[4 * maxX + 100], l[4 * maxX + 100], r[4 * maxX + 100], lzy[4 * maxX + 100];
void split (int &nod, int &f1, int &f2)
{
    if (lzy[nod] == 0) return ;
    lzy[f1] += lzy[nod], mi[f1] += lzy[nod];
    lzy[f2] += lzy[nod], mi[f2] += lzy[nod];
    lzy[nod] = 0;
}

void refresh (int &nod, int &f1, int &f2, int &mij, int &st, int &dr)
{
    if (mi[f1] == mi[f2])
        b[nod] = max ({b[f1], b[f2], r[f1] + l[f2]}),
        l[nod] = (l[f1] == mij - st + 1 ? l[f1] + l[f2] : l[f1]),
        r[nod] = (r[f2] == dr - mij ? r[f2] + r[f1] : r[f2]);
    else
    if (mi[f1] < mi[f2])
        b[nod] = b[f1],
        l[nod] = l[f1], r[nod] = 0;
    else
        b[nod] = b[f2],
        r[nod] = r[f2], l[nod] = 0;
}

void build (int nod, int st, int dr)
{
    mi[nod] = 0, l[nod] = r[nod] = b[nod] = dr - st + 1;
    if (st == dr) return ;
    int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
    build (f1, st, mij);
    build (f2, mij + 1, dr);
}

void update (int nod, int st, int dr, int x, int y, int xtra)
{
    if (x <= st && dr <= y)
    {
        mi[nod] += xtra, lzy[nod] += xtra;
        return ;
    }
    int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
    split (nod, f1, f2);
    if (x <= mij) update (f1, st, mij, x, y, xtra);
    if (mij < y) update (f2, mij + 1, dr, x, y, xtra);
    refresh (nod, f1, f2, mij, st, dr);
}

int query ()
{
    if (mi[1] != 0) return 0;
    return b[1];
}

void add (int y1, int y2, int sg)
{
    //printf ("[%d %d] %d\n", y1, y2, sg);
    update (1, 1, M, y1, y2, sg);
}

vector < pair < pair < int, int >, int > > v[maxX + 100];
void addLine (int line, int sg)
{
    for (auto it : v[line])
        if (sg * it.second > 0)
            add (it.first.first, it.first.second, it.second);
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d", &N, &M);
scanf ("%d", &budget);
scanf ("%d", &K), build (1, 1, M);
for (int i=1; i<=K; i++)
{
    int x1, y1, x2, y2, c;
    scanf ("%d %d %d %d %d", &x1, &y1, &x2, &y2, &c);
    if (budget == 0) c = (c > 0);
    v[x1].push_back ({{y1, y2}, +c});
    v[x2].push_back ({{y1, y2}, -c});
}
int L = 0, x2 = 0;
for (int x1=1; x1<=N - L; x1++)
{
    while (x2 < x1 + L)
        x2 ++, addLine (x2, +1);
    while (query () > L)
    {
        L ++;
        //printf ("%d %d  %d\n", x1, x2, query ());
        if (x2 < N)
            x2 ++, addLine (x2, +1);
        else
            break;
    }
    addLine (x1, -1);
}
printf ("%d\n", L);
return 0;
}

Compilation message

pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:80:7: 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:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d", &budget);
 ~~~~~~^~~~~~~~~~~~~~~
pyramid_base.cpp:82:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d", &K), build (1, 1, M);
 ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
pyramid_base.cpp:86:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d %d %d %d", &x1, &y1, &x2, &y2, &c);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23768 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23932 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24088 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 24640 KB Output is correct

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 62052 KB Output is correct
2 Correct 78 ms 62768 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 62768 KB Output is correct
2 Correct 70 ms 62768 KB Output is correct

Subtask #8
0 / 7.0

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

Subtask #9
0 / 7.0

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

Subtask #10
0 / 7.0

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

Subtask #11
0 / 7.0

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

Subtask #12
0 / 7.0

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

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1030 ms 75964 KB Output is correct
2 Correct 398 ms 75964 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1519 ms 79632 KB Output is correct
2 Correct 1463 ms 86848 KB Output is correct
3 Correct 700 ms 90988 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1591 ms 92092 KB Output is correct
2 Correct 2359 ms 110700 KB Output is correct
3 Correct 2187 ms 121512 KB Output is correct
4 Correct 1895 ms 131340 KB Output is correct
5 Correct 1169 ms 138552 KB Output is correct