oj.uz

답안 #52757

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
52757 2018-06-26T16:43:59 Z SpaimaCarpatilor Pyramid Base (IOI08_pyramid_base) C++17
10 / 100
 1691 ms 109984 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], r[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)
{
    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 + 1; 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:78: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:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d", &budget);
 ~~~~~~^~~~~~~~~~~~~~~
pyramid_base.cpp:80: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:84: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

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 23800 KB Output is correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 23920 KB Output isn't correct

Subtask #3
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 28 ms 23972 KB Output isn't correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 24780 KB Output isn't correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 29268 KB Output is correct

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 73 ms 61960 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 87 ms 61960 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 61960 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 78 ms 61960 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 163 ms 67012 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 159 ms 67308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 187 ms 68768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1041 ms 84408 KB Output is correct
2 Incorrect 422 ms 84408 KB Output isn't correct

Subtask #14
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1511 ms 101796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1691 ms 109984 KB Output isn't correct
2 Halted 0 ms 0 KB -