oj.uz

Submission #479375

# Submission time Handle Problem Language Result Execution time Memory
479375 2021-10-11T14:10:55 Z Alexandruabcde Fortune Telling 2 (JOI14_fortune_telling2) C++14
0 / 100
 10 ms 8396 KB 
#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 2e5 + 5;
constexpr int VALMAX = 3 * NMAX;
typedef long long LL;

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

int Op[NMAX];

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

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

int ce[NMAX];

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 * B[it];
            else Sum += 1LL * A[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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8140 KB Output is correct
2 Correct 9 ms 8396 KB Output is correct
3 Correct 10 ms 8268 KB Output is correct
4 Incorrect 10 ms 8268 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8140 KB Output is correct
2 Correct 9 ms 8396 KB Output is correct
3 Correct 10 ms 8268 KB Output is correct
4 Incorrect 10 ms 8268 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8140 KB Output is correct
2 Correct 9 ms 8396 KB Output is correct
3 Correct 10 ms 8268 KB Output is correct
4 Incorrect 10 ms 8268 KB Output isn't correct
5 Halted 0 ms 0 KB -