답안 #53010

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
53010 2018-06-27T15:20:08 Z Alexa2001 Pyramid Base (IOI08_pyramid_base) C++17
100 / 100
3843 ms 141364 KB
#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;

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(L[node] == -1) return;

            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;
        }

        int query2()
        {
            return mn[1];
        }

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

            if(st == dr) return;

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

namespace solve0
{
    vector< pair<int,int> > start[Nmax], finish[Nmax];
    SegmentTree aint;

    void compute()
    {
        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';
    }
}

namespace solve1
{
    int Cost[Nmax], X1[Nmax], X2[Nmax], Y1[Nmax], Y2[Nmax];
    vector< pair< pair<int,int> , int > > event[Nmax];
    SegmentTree aint;

    int need(int L)
    {
        int i, ans = INT_MAX, x, y, ym;
        for(i=1; i<=N; ++i) event[i].clear();

        for(i=1; i<=n; ++i)
        {
            x = max(1, X1[i] - L + 1);
            y = max(1, Y1[i] - L + 1);
            ym = min(Y2[i], M - L + 1);
            event[x].push_back({ {y, ym}, Cost[i] });
            event[X2[i] + 1].push_back({ {y, ym}, -Cost[i] });
        }

        aint.build(1, 1, M-L+1, 1);

        for(i=1; i<=N-L+1; ++i)
        {
            for(auto ev : event[i])
                aint.update(1, 1, M-L+1, ev.first.first, ev.first.second, ev.second);
            ans = min(ans, aint.query2());
        }
        return ans;
    }

    void compute()
    {
        int i;
        for(i=1; i<=n; ++i) cin >> X1[i] >> Y1[i] >> X2[i] >> Y2[i] >> Cost[i];

        int st = 1, dr = min(N, M);
        while(st<=dr)
        {
            if(need(mid) <= money) st = mid+1;
                else dr = mid-1;
        }

        cout << dr << '\n';
    }
}

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

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

    if(!money) solve0 :: compute(); /// subtask 1 + 3
        else solve1 :: compute(); /// subtask 2

    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 70836 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 71024 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 71024 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 71668 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 76168 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 112100 KB Output is correct
2 Correct 120 ms 112124 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 121 ms 112136 KB Output is correct
2 Correct 117 ms 112180 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 112180 KB Output is correct
2 Correct 140 ms 112180 KB Output is correct
3 Correct 129 ms 112180 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 501 ms 112180 KB Output is correct
2 Correct 830 ms 112180 KB Output is correct
3 Correct 590 ms 112180 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1355 ms 112180 KB Output is correct
2 Correct 225 ms 112180 KB Output is correct
3 Correct 755 ms 115620 KB Output is correct
4 Correct 2982 ms 123632 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1912 ms 123632 KB Output is correct
2 Correct 3120 ms 126808 KB Output is correct
3 Correct 801 ms 126808 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1346 ms 126808 KB Output is correct
2 Correct 3782 ms 130708 KB Output is correct
3 Correct 3843 ms 131228 KB Output is correct
4 Correct 3592 ms 132324 KB Output is correct
5 Correct 3758 ms 133380 KB Output is correct
6 Correct 446 ms 133380 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1070 ms 133380 KB Output is correct
2 Correct 491 ms 133380 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1504 ms 136752 KB Output is correct
2 Correct 1435 ms 136752 KB Output is correct
3 Correct 832 ms 136752 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2001 ms 141364 KB Output is correct
2 Correct 2047 ms 141364 KB Output is correct
3 Correct 1905 ms 141364 KB Output is correct
4 Correct 1908 ms 141364 KB Output is correct
5 Correct 1090 ms 141364 KB Output is correct