Submission #479383

#	Time	Username	Problem	Language	Result	Execution time	Memory
479383		Alexandruabcde	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	4 / 100	112 ms	26436 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 2e5 + 5;
constexpr int VALMAX = 1e6 + 5;
typedef long long LL;

int N, K;
int A[NMAX];
int B[NMAX];

int Op[NMAX];

vector <int> Last_Pos[NMAX];
int Aint[4*VALMAX];

int Vf = 0;
int Norm_A[NMAX];
int Norm_B[NMAX];
int Norm_Op[NMAX];

void Update_Max (int nod, int a, int b, int poz, int val) {
    if (a == b) {
        Aint[nod] = val;
        return;
    }

    int mij = (a + b) / 2;

    if (poz <= mij) Update_Max(2*nod, a, mij, poz, val);
    else Update_Max(2*nod+1, mij+1, b, poz, val);

    Aint[nod] = max(Aint[2*nod], Aint[2*nod+1]);
}

int Query_Max (int nod, int a, int b, int qa, int qb) {
    if (qa <= a && b <= qb) return Aint[nod];

    int mij = (a + b) / 2;
    int ans_1 = 0, ans_2 = 0;

    if (qa <= mij) ans_1 = Query_Max(2*nod, a, mij, qa, qb);
    if (mij < qb) ans_2 = Query_Max(2*nod+1, mij+1, b, qa, qb);

    return max(ans_1, ans_2);
}

void Update_Add (int nod, int a, int b, int poz, int val) {
    if (a == b) {
        Aint[nod] = val;
        return;
    }

    int mij = (a + b) / 2;

    if (poz <= mij) Update_Add(2*nod, a, mij, poz, val);
    else Update_Add(2*nod+1, mij+1, b, poz, val);

    Aint[nod] = Aint[2*nod] + Aint[2*nod+1];
}

int Query_Add (int nod, int a, int b, int qa, int qb) {
    if (qa <= a && b <= qb) return Aint[nod];

    int mij = (a + b) / 2;
    int ans_1 = 0, ans_2 = 0;

    if (qa <= mij) ans_1 = Query_Add(2*nod, a, mij, qa, qb);
    if (mij < qb) ans_2 = Query_Add(2*nod+1, mij+1, b, qa, qb);

    return ans_1 + ans_2;
}

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

    cin >> N >> K;

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

    for (int i = 1; i <= K; ++ i )
        cin >> Op[i];
}

void Normalize () {
    map <int, int> mp;
    for (int i = 1; i <= N; ++ i )
        mp[A[i]] = mp[B[i]] = 1;

    for (int i = 1; i <= K; ++ i )
        mp[Op[i]] = 1;

    Vf = 0;

    for (auto &it : mp)
        it.second = ++Vf;

    for (int i = 1; i <= N; ++ i ) {
        Norm_A[i] = mp[A[i]];
        Norm_B[i] = mp[B[i]];
    }

    for (int i = 1; i <= K; ++ i )
        Norm_Op[i] = mp[Op[i]];
}

void Solve () {
    Normalize();

    for (int i = 1; i <= K; ++ i )
        Update_Max(1, 1, Vf, Norm_Op[i], i);

    for (int i = 1; i <= N; ++ i ) {
        int st = min(Norm_A[i], Norm_B[i]);
        int dr = max(Norm_A[i], Norm_B[i]);

        Last_Pos[Query_Max(1, 1, Vf, st, dr-1)].push_back(i);
    }

    memset(Aint, 0, sizeof(Aint));

    LL Sum = 0;

    for (int i = K; i >= 1; -- i ) {
        for (auto it : Last_Pos[i]) {
            int dr = max(Norm_A[it], Norm_B[it]);

            int ans = Query_Add(1, 1, Vf, dr, Vf);

            if (A[it] <= B[it]) {
                if (ans % 2 == 0) Sum += 1LL * B[it];
                else Sum += 1LL * A[it];
            }
            else {
                if (ans % 2 == 0) Sum += 1LL * A[it];
                else Sum += 1LL * B[it];
            }
        }
        Update_Add(1, 1, Vf, Norm_Op[i], 1);
    }

    for (auto it : Last_Pos[0]) {
        int dr = max(Norm_A[it], Norm_B[it]);

        int ans = Query_Add(1, 1, Vf, dr, Vf);

        if (A[it] <= B[it]) {
            if (ans % 2 == 0) Sum += 1LL * A[it];
            else Sum += 1LL * B[it];
        }
        else {
            if (ans % 2 == 0) Sum += 1LL * A[it];
            else Sum += 1LL * B[it];
        }
    }

    cout << Sum << '\n';
}

int main () {
    Read();
    Solve();

    return 0;
}

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