oj.uz

Submission #719871

# Submission time Handle Problem Language Result Execution time Memory
719871 2023-04-06T23:48:20 Z ThegeekKnight16 Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 1037 ms 206608 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int border = 1e9 + 10;
vector<int> minTmp, qnt, e, d;

int create()
{
    minTmp.push_back(LONG_LONG_MAX);
    qnt.push_back(0);
    e.push_back(0);
    d.push_back(0);
    return qnt.size()-1;
}

void copy(int pos, int novo)
{
    minTmp[novo] = minTmp[pos];
    qnt[novo] = qnt[pos];
    e[novo] = e[pos];
    d[novo] = d[pos];
}

int update(int pos, int ini, int fim, int id, int val)
{
    if (id < ini || id > fim) return pos;
    int novo = create();
    copy(pos, novo);
    if (ini == fim)
    {
        qnt[novo]++;
        minTmp[novo] = min(minTmp[novo], val);
        return novo;
    }
    int m = (ini + fim) >> 1;
    if (id <= m) e[novo] = update(e[novo], ini, m, id, val);
    else d[novo] = update(d[novo], m+1, fim, id, val);

    qnt[novo] = qnt[e[novo]] + qnt[d[novo]];
    minTmp[novo] = min(minTmp[e[novo]], minTmp[d[novo]]);
    return novo;
}

pair<int, int> query(int pos, int ini, int fim, int p, int q)
{
    if (q < ini || p > fim) return make_pair(0, LONG_LONG_MAX);
    if (pos == 0) return make_pair(0, LONG_LONG_MAX);
    if (p <= ini && fim <= q) return make_pair(qnt[pos], minTmp[pos]);
    int m = (ini + fim) >> 1;
    pair<int, int> respE = query(e[pos], ini,  m , p, q);
    pair<int, int> respD = query(d[pos], m+1, fim, p, q);
    return make_pair(respE.first + respD.first, min(respE.second, respD.second));
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, K;
    cin >> N >> K;
    vector<pair<int, int> > v(N);
    for (auto &[x, y] : v) cin >> x >> y;
    int ans = 0LL;
    // while (v.size() > K) {ans += v.back().first; v.pop_back();}

    // reverse(v.begin(), v.end());
    // v.emplace_back(0, 0);
    // reverse(v.begin(), v.end());

    vector<int> Oper(K);
    for (auto &x : Oper) cin >> x;
    Oper.push_back(-1);
    reverse(Oper.begin(), Oper.end());

    vector<int> Raiz(K+1);
    Raiz[0] = create();
    for (int i = 1; i <= K; i++) Raiz[i] = update(Raiz[i-1], 1, border, Oper[i], i);

    for (auto [x, y] : v)
    {
        int resp = 1;
        if (x > y) {resp--; swap(x, y);}

        auto [qntMeio, minMeio] = query(Raiz[K], 1, border, x, y-1);
        if (qntMeio == 0) minMeio = K;
        else resp = 0;

        if (minMeio == LONG_LONG_MAX) minMeio = K;

        auto [qntMaior, minMaior] = query(Raiz[minMeio], 1, border, y, border);
        resp += qntMaior;

        // cerr << i << " " << qntMeio << " " << minMeio << " " << qntMaior << " " << resp << '\n';

        ans += ((resp % 2) ? x : y);
    }

    cout << ans << '\n';
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1356 KB Output is correct
2 Correct 3 ms 1384 KB Output is correct
3 Correct 3 ms 1484 KB Output is correct
4 Correct 3 ms 1512 KB Output is correct
5 Correct 2 ms 1484 KB Output is correct
6 Correct 3 ms 1484 KB Output is correct
7 Correct 3 ms 1484 KB Output is correct
8 Correct 3 ms 1472 KB Output is correct
9 Correct 2 ms 1484 KB Output is correct
10 Correct 2 ms 1468 KB Output is correct
11 Correct 3 ms 1484 KB Output is correct
12 Correct 3 ms 1512 KB Output is correct
13 Correct 3 ms 1484 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1356 KB Output is correct
2 Correct 3 ms 1384 KB Output is correct
3 Correct 3 ms 1484 KB Output is correct
4 Correct 3 ms 1512 KB Output is correct
5 Correct 2 ms 1484 KB Output is correct
6 Correct 3 ms 1484 KB Output is correct
7 Correct 3 ms 1484 KB Output is correct
8 Correct 3 ms 1472 KB Output is correct
9 Correct 2 ms 1484 KB Output is correct
10 Correct 2 ms 1468 KB Output is correct
11 Correct 3 ms 1484 KB Output is correct
12 Correct 3 ms 1512 KB Output is correct
13 Correct 3 ms 1484 KB Output is correct
14 Correct 29 ms 11356 KB Output is correct
15 Correct 62 ms 22184 KB Output is correct
16 Correct 91 ms 31280 KB Output is correct
17 Correct 135 ms 43992 KB Output is correct
18 Correct 139 ms 43920 KB Output is correct
19 Correct 136 ms 44000 KB Output is correct
20 Correct 137 ms 43984 KB Output is correct
21 Correct 122 ms 43916 KB Output is correct
22 Correct 115 ms 43472 KB Output is correct
23 Correct 118 ms 43412 KB Output is correct
24 Correct 116 ms 43496 KB Output is correct
25 Correct 114 ms 43548 KB Output is correct
26 Correct 111 ms 43844 KB Output is correct
27 Correct 125 ms 43984 KB Output is correct
28 Correct 116 ms 43996 KB Output is correct
29 Correct 135 ms 44100 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1356 KB Output is correct
2 Correct 3 ms 1384 KB Output is correct
3 Correct 3 ms 1484 KB Output is correct
4 Correct 3 ms 1512 KB Output is correct
5 Correct 2 ms 1484 KB Output is correct
6 Correct 3 ms 1484 KB Output is correct
7 Correct 3 ms 1484 KB Output is correct
8 Correct 3 ms 1472 KB Output is correct
9 Correct 2 ms 1484 KB Output is correct
10 Correct 2 ms 1468 KB Output is correct
11 Correct 3 ms 1484 KB Output is correct
12 Correct 3 ms 1512 KB Output is correct
13 Correct 3 ms 1484 KB Output is correct
14 Correct 29 ms 11356 KB Output is correct
15 Correct 62 ms 22184 KB Output is correct
16 Correct 91 ms 31280 KB Output is correct
17 Correct 135 ms 43992 KB Output is correct
18 Correct 139 ms 43920 KB Output is correct
19 Correct 136 ms 44000 KB Output is correct
20 Correct 137 ms 43984 KB Output is correct
21 Correct 122 ms 43916 KB Output is correct
22 Correct 115 ms 43472 KB Output is correct
23 Correct 118 ms 43412 KB Output is correct
24 Correct 116 ms 43496 KB Output is correct
25 Correct 114 ms 43548 KB Output is correct
26 Correct 111 ms 43844 KB Output is correct
27 Correct 125 ms 43984 KB Output is correct
28 Correct 116 ms 43996 KB Output is correct
29 Correct 135 ms 44100 KB Output is correct
30 Correct 505 ms 199448 KB Output is correct
31 Correct 602 ms 201036 KB Output is correct
32 Correct 679 ms 202736 KB Output is correct
33 Correct 879 ms 206188 KB Output is correct
34 Correct 493 ms 199160 KB Output is correct
35 Correct 851 ms 206260 KB Output is correct
36 Correct 864 ms 206284 KB Output is correct
37 Correct 1037 ms 206328 KB Output is correct
38 Correct 917 ms 206224 KB Output is correct
39 Correct 882 ms 206364 KB Output is correct
40 Correct 751 ms 205924 KB Output is correct
41 Correct 853 ms 206192 KB Output is correct
42 Correct 855 ms 206204 KB Output is correct
43 Correct 573 ms 205516 KB Output is correct
44 Correct 583 ms 205544 KB Output is correct
45 Correct 572 ms 205448 KB Output is correct
46 Correct 624 ms 204364 KB Output is correct
47 Correct 621 ms 204192 KB Output is correct
48 Correct 676 ms 206244 KB Output is correct
49 Correct 689 ms 206608 KB Output is correct