oj.uz

답안 #219094

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
219094 2020-04-03T16:38:11 Z andreiomd 운세 보기 2 (JOI14_fortune_telling2) C++11
0 / 100
 7 ms 5120 KB 
#include <iostream>
#include <algorithm>
#include <vector>

#include <cassert>

using namespace std;

typedef pair < int, int > PII;

const int NMAX = 2e5 + 5, KMAX = 2e5 + 5;

int N, K;

PII A[NMAX];

int T[KMAX];

int q;
PII V[KMAX], Q[KMAX];

vector < PII > Queries[NMAX];

/// Fenwick Tree:
int AIB[KMAX];

static inline int UB (int X)
{
    return (X & (-X));
}

static inline void Update_1 (int pos, int val)
{
    for(int i = pos; i <= q; i += UB(i))
        AIB[i] += val;

    return;
}

static inline int Query_1 (int pos)
{
    int r = 0;

    for(int i = pos; i >= 1; i -= UB(i))
        r += AIB[i];

    return r;
}
///

/// Segment Tree:
int AINT[4 * KMAX];

static inline void Update (int Node, int a, int b, int pos, int val)
{
    if(a == b)
    {
        AINT[Node] = val;

        return;
    }

    int Mid = (a + b) >> 1;

    if(pos <= Mid)
        Update(2 * Node, a, Mid, pos, val);

    if(pos > Mid)
        Update(2 * Node + 1, Mid + 1, b, pos, val);

    AINT[Node] = max(AINT[2 * Node], AINT[2 * Node + 1]);

    return;
}

static inline int Query (int Node, int a, int b, int qa, int qb)
{
    if(qa <= a && b <= qb)
        return AINT[Node];

    int Mid = (a + b) >> 1;

    int p1 = 0, p2 = 0;

    if(qa <= Mid)
        p1 = Query(2 * Node, a, Mid, qa, qb);

    if(qb > Mid)
        p2 = Query(2 * Node + 1, Mid + 1, b, qa, qb);

    return max(p1, p2);
}
///

static inline void Read ()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> K;

    for(int i = 1; i <= N; ++i)
        cin >> A[i].first >> A[i].second;

    for(int i = 1; i <= K; ++i)
        cin >> T[i], V[i] = {T[i], i};

    return;
}

auto cmp = [] (PII A, PII B)
{
    if(A.first < B.first)
        return 1;

    if(A.first > B.first)
        return 0;

    if(A.second > B.second)
        return 1;

    return 0;
};

static inline void Precalculation ()
{
    sort(V + 1, V + K + 1, cmp);

    Q[++q] = V[1];
    for(int i = 2; i <= K; ++i)
        if(V[i].first != V[i - 1].first)
            Q[++q] = V[i];

    for(int i = 1; i <= q; ++i)
        Update(1, 1, q, i, Q[i].second);

    return;
}

static inline int CB1 (int X)
{
    int Left = 1, Right = q, ans = -1;

    while(Left <= Right)
    {
        int Mid = (Left + Right) >> 1;

        if(Q[Mid].first >= X)
        {
            ans = Mid;

            Right = Mid - 1;
        }
        else
            Left = Mid + 1;
    }

    return ans;
}

static inline int CB2 (int X)
{
    int Left = 1, Right = q, ans = -1;

    while(Left <= Right)
    {
        int Mid = (Left + Right) >> 1;

        if(Q[Mid].first <= X)
        {
            ans = Mid;

            Left = Mid + 1;
        }
        else
            Right = Mid - 1;
    }

    return ans;
}

static inline int Lower (int X)
{
    int Left = 1, Right = q, ans = -1;

    while(Left <= Right)
    {
        int Mid = (Left + Right) >> 1;

        if(Q[Mid].first >= X)
        {
            ans = Mid;

            Right = Mid - 1;
        }
        else
            Left = Mid + 1;
    }

    return ans;
}

static inline void Solve ()
{
    long long ans = 0;

    for(int i = 1; i <= N; ++i)
    {
        int Last_Index = 0;

        int Min = min(A[i].first, A[i].second);
        int Max = max(A[i].first, A[i].second);

        int p1 = CB1(Min);
        int p2 = CB2(Max - 1);

        if(p1 == -1 || (p1 > 0 && Q[p1].first >= Max))
            Last_Index = 0;
        else
            Last_Index = Query(1, 1, q, p1, p2);

        if(Last_Index && A[i].first < A[i].second)
            swap(A[i].first, A[i].second);

        /*
        int counts = 0;

        for(int j = Last_Index + 1; j <= K; ++j)
            if(T[j] >= Max)
                ++counts;

        if(counts & 1)
            swap(A[i].first, A[i].second);

        ans += 1LL * A[i].first;
        */

        Queries[Last_Index + 1].push_back({Max, i});
    }

    for(int i = K; i >= 1; --i)
        if(!Queries[i].empty())
        {
            int pos = Lower(T[i]);
            Update_1(pos, 1);

            assert(Q[pos].first == T[i]);

            for(auto it : Queries[i])
            {
                int Val = it.first;
                int j = it.second;

                int counts = Query_1(q) - Query_1(CB1(Val) - 1);

                if(counts & 1)
                    swap(A[j].first, A[j].second);

                ans += 1LL * A[j].first;
            }
        }

    cout << ans << '\n';

    return;
}

int main()
{
    Read();

    Precalculation();

    Solve();

    return 0;
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 31.0

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

Subtask #3
0 / 65.0

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