Submission #219073

#	Time	Username	Problem	Language	Result	Execution time	Memory
219073		andreiomd	Fortune Telling 2 (JOI14_fortune_telling2)	C++11	0 / 100	5 ms	384 KiB

fortune_telling2

#include <iostream>
#include <algorithm>

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[NMAX], Q[NMAX];

int AINT[4 * NMAX];

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 void Solve ()
{
    long long ans = 0;

    for(int i = 1; i <= N; ++i)
    {
        int Min = min(A[i].first, A[i].second);
        int Max = max(A[i].first, A[i].second);

        int Last = 0;

        int p = CB2(Max - 1);

        if(p == -1)
        {
            int cnt = 0;

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

            if(cnt & 1)
                ans += 1LL * A[i].second;
            else
                ans += 1LL * A[i].first;

            continue;
        }

        int Start = CB1(Min);

        int Ind_Last = Query(1, 1, q, Start, p);

        int cnt = 0;

        for(int j = Ind_Last + 1; j <= q; ++j)
            if(T[j] >= Max)
                ++cnt;

        if(cnt & 1)
            ans += 1LL * A[i].second;
        else
            ans += 1LL * A[i].first;
    }

    cout << ans << '\n';

    return;
}

int main()
{
    Read();

    Precalculation();

    Solve();

    return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'void Solve()':
fortune_telling2.cpp:157:13: warning: unused variable 'Last' [-Wunused-variable]
         int Last = 0;
             ^~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 31
• Subtask 3: 0 / 65