oj.uz

Submission #479383

# Submission time Handle Problem Language Result Execution time Memory
479383 2021-10-11T14:38:30 Z Alexandruabcde Fortune Telling 2 (JOI14_fortune_telling2) C++14
4 / 100
 112 ms 26436 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20684 KB Output is correct
2 Correct 14 ms 20776 KB Output is correct
3 Correct 15 ms 20876 KB Output is correct
4 Correct 15 ms 20892 KB Output is correct
5 Correct 14 ms 20864 KB Output is correct
6 Correct 15 ms 20780 KB Output is correct
7 Correct 14 ms 20792 KB Output is correct
8 Correct 14 ms 20784 KB Output is correct
9 Correct 14 ms 20784 KB Output is correct
10 Correct 15 ms 20684 KB Output is correct
11 Correct 14 ms 20812 KB Output is correct
12 Correct 14 ms 20816 KB Output is correct
13 Correct 14 ms 20816 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20684 KB Output is correct
2 Correct 14 ms 20776 KB Output is correct
3 Correct 15 ms 20876 KB Output is correct
4 Correct 15 ms 20892 KB Output is correct
5 Correct 14 ms 20864 KB Output is correct
6 Correct 15 ms 20780 KB Output is correct
7 Correct 14 ms 20792 KB Output is correct
8 Correct 14 ms 20784 KB Output is correct
9 Correct 14 ms 20784 KB Output is correct
10 Correct 15 ms 20684 KB Output is correct
11 Correct 14 ms 20812 KB Output is correct
12 Correct 14 ms 20816 KB Output is correct
13 Correct 14 ms 20816 KB Output is correct
14 Correct 38 ms 22568 KB Output is correct
15 Correct 71 ms 24572 KB Output is correct
16 Incorrect 112 ms 26436 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 20684 KB Output is correct
2 Correct 14 ms 20776 KB Output is correct
3 Correct 15 ms 20876 KB Output is correct
4 Correct 15 ms 20892 KB Output is correct
5 Correct 14 ms 20864 KB Output is correct
6 Correct 15 ms 20780 KB Output is correct
7 Correct 14 ms 20792 KB Output is correct
8 Correct 14 ms 20784 KB Output is correct
9 Correct 14 ms 20784 KB Output is correct
10 Correct 15 ms 20684 KB Output is correct
11 Correct 14 ms 20812 KB Output is correct
12 Correct 14 ms 20816 KB Output is correct
13 Correct 14 ms 20816 KB Output is correct
14 Correct 38 ms 22568 KB Output is correct
15 Correct 71 ms 24572 KB Output is correct
16 Incorrect 112 ms 26436 KB Output isn't correct
17 Halted 0 ms 0 KB -