답안 #52985 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52985	2018-06-27T13:04:13 Z	Alexa2001	Pyramid Base (IOI08_pyramid_base)	C++17	65 / 100	1975 ms	109680 KB

pyramid_base

#include <bits/stdc++.h>
#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)

using namespace std;

const int Nmax = 1e6 + 5;

int n, N, M, money;
vector< pair<int,int> > start[Nmax], finish[Nmax];

class SegmentTree
{
    int lazy[Nmax<<2], L[Nmax<<2], R[Nmax<<2], best[Nmax<<2], mn[Nmax<<2];

    public:
        void update(int node, int st, int dr, int Left, int Right, int add)
        {
            if(Left<=st && dr<=Right)
            {
                mn[node] += add;
                lazy[node] += add;
                return;
            }

            if(lazy[node])
            {
                lazy[left_son] += lazy[node];
                lazy[right_son] += lazy[node];
                mn[left_son] += lazy[node];
                mn[right_son] += lazy[node];
                lazy[node] = 0;
            }

            if(Left<=mid) update(left_son, st, mid, Left, Right, add);
            if(mid<Right) update(right_son, mid+1, dr, Left, Right, add);

            mn[node] = min(mn[left_son], mn[right_son]);

            if(mn[left_son] == mn[right_son])
            {
                L[node] = L[left_son] + (L[left_son] == mid-st+1 ? L[right_son] : 0);
                R[node] = R[right_son] + (R[right_son] == dr-mid ? R[left_son] : 0);
                best[node] = max(best[left_son], best[right_son]);
                best[node] = max(best[node], R[left_son] + L[right_son]);
            }
            else if(mn[node] == mn[left_son])
            {
                L[node] = L[left_son];
                R[node] = 0;
                best[node] = best[left_son];
            }
            else
            {
                L[node] = 0;
                R[node] = R[right_son];
                best[node] = best[right_son];
            }
        }

        int query()
        {
            return mn[1] == 0 ? best[1] : 0;
        }

        void build(int node, int st, int dr)
        {
            mn[node] = lazy[node] = 0;
            L[node] = R[node] = best[node] = dr-st+1;

            if(st == dr) return;

            build(left_son, st, mid);
            build(right_son, mid+1, dr);
        }
} aint;

void solve0()
{
    int i, j, X1, Y1, X2, Y2, C;
    int ans = 0;

    aint.build(1, 1, M);

    for(i=1; i<=n; ++i)
    {
        cin >> X1 >> Y1 >> X2 >> Y2 >> C;
        start[X1].push_back({Y1, Y2});
        finish[X2].push_back({Y1, Y2});
    }

    j = 0;
    for(i=1; i<=N; ++i)
        if(i==1 || !finish[i-1].empty())
        {
            for(auto e : finish[i-1])
                aint.update(1, 1, M, e.first, e.second, -1);

            while(j+1 <= N && aint.query() >= j-i+1)
            {
                ++j;
                for(auto e : start[j])
                    aint.update(1, 1, M, e.first, e.second, 1);
            }

            if(j == N && aint.query() >= N-i+1)
            {
                ans = max(ans, N-i+1);
                break;
            }

            ans = max(ans, j-i);
        }
    cout << ans << '\n';
}

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

    cin >> N >> M >> money >> n;

    if(!money) solve0(); /// subtask 1 + 3
      //  else solve(); /// subtask 2

    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	95 ms	88660 KB	Output is correct
2	Correct	94 ms	88736 KB	Output is correct

Subtask #7
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	97 ms	88752 KB	Output is correct
2	Correct	98 ms	88752 KB	Output is correct

Subtask #8
0 / 7.0

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

Subtask #9
0 / 7.0

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

Subtask #10
0 / 7.0

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

Subtask #11
0 / 7.0

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

Subtask #12
0 / 7.0

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

Subtask #13
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1016 ms	100008 KB	Output is correct
2	Correct	423 ms	100008 KB	Output is correct

Subtask #14
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1207 ms	105020 KB	Output is correct
2	Correct	1553 ms	105020 KB	Output is correct
3	Correct	709 ms	105020 KB	Output is correct

Subtask #15
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1975 ms	109680 KB	Output is correct
2	Correct	1936 ms	109680 KB	Output is correct
3	Correct	1928 ms	109680 KB	Output is correct
4	Correct	1906 ms	109680 KB	Output is correct
5	Correct	1026 ms	109680 KB	Output is correct

답안 #52985

Compilation message