oj.uz

Submission #954921

# Submission time Handle Problem Language Result Execution time Memory
954921 2024-03-28T19:47:04 Z hariaakas646 Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 1164 ms 108740 KB 
#include <bits/stdc++.h>

using namespace std;

#define scd(t) scanf("%d", &t)
#define sclld(t) scanf("%lld", &t)
#define forr(i, j, k) for (int i = j; i < k; i++)
#define frange(i, j) forr(i, 0, j)
#define all(cont) cont.begin(), cont.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
typedef long long int lli;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<lli> vll;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef map<int, int> mpii;
typedef set<int> seti;
typedef multiset<int> mseti;
typedef long double ld;


void usaco()
{
    freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
//    freopen("problem.out", "w", stdout);
}

template <class T>
struct BIT
{
    int size;
    vector<T> bit;
    vector<T> vec;

    BIT(int n) : size(n), bit(n + 1), vec(n + 1) {}

    int lsb(int x)
    {
        return x & (-x);
    }

    void set(int id, T v)
    {
        add(id, v - vec[id]);
    }

    void add(int id, T v)
    {
        if (id == 0)
            return;
        vec[id] += v;
        while (id <= size)
        {
            bit[id] += v;
            id += lsb(id);
        }
    }

    T query(int id)
    {
        T tot = 0;
        if (id == 0)
            return tot;
        while (id >= 1)
        {
            tot += bit[id];
            id -= lsb(id);
        }
        return tot;
    }
};

template <class T>
struct SegTree
{
    int size = 1, n;
    vector<T> segtree;
    vector<T> vec;

    T def; // Assign a value

    void init(int l, T defv)
    {
        n = l;
        def = defv;

        while (size < n)
            size *= 2;

        segtree.assign(2 * size, def);
        vec.assign(size, def);
    }

    T operation(T x, T y)
    {
        return max(x, y); // Any required operation
    }

    void recalculate(int x)
    {
        segtree[x] = operation(segtree[2 * x + 1], segtree[2 * x + 2]);
    }

    void build(int x, int l, int r)
    {
        if (l == r)
        {
            segtree[x] = vec[l];
            return;
        }
        int mid = (l + r) / 2;
        build(2 * x + 1, l, mid);
        build(2 * x + 2, mid + 1, r);
        recalculate(x);
    }

    void build()
    {
        build(0, 0, size - 1);
    }

    void set(int id, T val)
    {
        vec[id] = val;
    }

    void update(int x, int l, int r, int id, T val)
    {
        if (l == r)
        {
            segtree[x] = val;
            return;
        }
        int mid = (l + r) / 2;
        if (id <= mid)
        {
            update(2 * x + 1, l, mid, id, val);
        }
        else
        {
            update(2 * x + 2, mid + 1, r, id, val);
        }
        recalculate(x);
    }

    void update(int id, T val)
    {
        update(0, 0, size - 1, id, val);
    }

    T query(int x, int l, int r, int lx, int rx)
    {
        if (lx > r || rx < l)
        {
            return def;
        }
        if (lx <= l && r <= rx)
        {
            return segtree[x];
        }
        int mid = (l + r) / 2;
        T v1 = query(2 * x + 1, l, mid, lx, rx);
        T v2 = query(2 * x + 2, mid + 1, r, lx, rx);
        return operation(v1, v2);
    }

    T query(int lx, int rx)
    {
        return query(0, 0, size - 1, lx, rx);
    }
};

bool cmp(pii x, pii y) {
    return max(x.f, x.s) > max(y.f, y.s);
}

int main() {
    // usaco();
    int n, k;
    scd(n);
    scd(k);
    vii vec(n);
    seti st;

    frange(i, n) {
        scd(vec[i].f);
        scd(vec[i].s);
        st.insert(vec[i].f);
        st.insert(vec[i].s);
    }

    vi val(k+1);
    vii val2;
    forr(i, 1, k+1) {
        scd(val[i]);
        st.insert(val[i]);
        val2.pb(mp(val[i], i));
    }
    sort(all(val2));
    mpii mv1, mv2;

    int id = 0;
    for(auto e : st) {
        mv2[id] = e;
        mv1[e] = id++;
    }

    SegTree<int> tree;
    tree.init(id, 0);
    forr(i, 1, k+1) {
        tree.set(mv1[val[i]], i);
    }
    tree.build();

    BIT<int> bit(k+1);

    sort(all(vec), cmp);

    lli tot = 0;
    id =val2.size();
    for(auto p : vec) {
        int a = max(p.f, p.s);
        int b = min(p.f, p.s);
        if(a == b) {
            tot += a;
            continue;
        }
        // printf("%d %d\n", id, val2[id-1].f);
        while(id > 0 && val2[id-1].f >= a) {
            id--;
            // printf("%d\n", id);
            bit.add(val2[id].s, 1);
        }
        int id1 = tree.query(mv1[b], mv1[a]-1);
        // printf("%d ", id1);
        if(id1 == 0) {
            int x = bit.query(k);
            // printf("%d %d %d\n", x, p.f, p.s);
            if(x % 2 == 0) tot += p.f;
            else tot += p.s;
        }
        else {
            int x = bit.query(k) - bit.query(id1);
            // printf("%d %d %d\n", x, p.f, p.s);
            if(x % 2 == 0) tot += a;
            else tot += b;
        }
    }
    printf("%lld", tot);

}

Compilation message

fortune_telling2.cpp: In function 'void usaco()':
fortune_telling2.cpp:30:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
fortune_telling2.cpp:186:5: note: in expansion of macro 'scd'
  186 |     scd(n);
      |     ^~~
fortune_telling2.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
fortune_telling2.cpp:187:5: note: in expansion of macro 'scd'
  187 |     scd(k);
      |     ^~~
fortune_telling2.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
fortune_telling2.cpp:192:9: note: in expansion of macro 'scd'
  192 |         scd(vec[i].f);
      |         ^~~
fortune_telling2.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
fortune_telling2.cpp:193:9: note: in expansion of macro 'scd'
  193 |         scd(vec[i].s);
      |         ^~~
fortune_telling2.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
fortune_telling2.cpp:201:9: note: in expansion of macro 'scd'
  201 |         scd(val[i]);
      |         ^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 956 KB Output is correct
8 Correct 2 ms 756 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 600 KB Output is correct
13 Correct 2 ms 844 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 956 KB Output is correct
8 Correct 2 ms 756 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 600 KB Output is correct
13 Correct 2 ms 844 KB Output is correct
14 Correct 25 ms 5464 KB Output is correct
15 Correct 54 ms 10616 KB Output is correct
16 Correct 90 ms 16148 KB Output is correct
17 Correct 123 ms 20940 KB Output is correct
18 Correct 133 ms 20936 KB Output is correct
19 Correct 135 ms 21192 KB Output is correct
20 Correct 123 ms 20940 KB Output is correct
21 Correct 118 ms 20952 KB Output is correct
22 Correct 80 ms 14792 KB Output is correct
23 Correct 73 ms 11604 KB Output is correct
24 Correct 59 ms 9156 KB Output is correct
25 Correct 83 ms 16620 KB Output is correct
26 Correct 73 ms 14284 KB Output is correct
27 Correct 83 ms 15304 KB Output is correct
28 Correct 82 ms 15560 KB Output is correct
29 Correct 98 ms 18120 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 956 KB Output is correct
8 Correct 2 ms 756 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 600 KB Output is correct
13 Correct 2 ms 844 KB Output is correct
14 Correct 25 ms 5464 KB Output is correct
15 Correct 54 ms 10616 KB Output is correct
16 Correct 90 ms 16148 KB Output is correct
17 Correct 123 ms 20940 KB Output is correct
18 Correct 133 ms 20936 KB Output is correct
19 Correct 135 ms 21192 KB Output is correct
20 Correct 123 ms 20940 KB Output is correct
21 Correct 118 ms 20952 KB Output is correct
22 Correct 80 ms 14792 KB Output is correct
23 Correct 73 ms 11604 KB Output is correct
24 Correct 59 ms 9156 KB Output is correct
25 Correct 83 ms 16620 KB Output is correct
26 Correct 73 ms 14284 KB Output is correct
27 Correct 83 ms 15304 KB Output is correct
28 Correct 82 ms 15560 KB Output is correct
29 Correct 98 ms 18120 KB Output is correct
30 Correct 306 ms 40644 KB Output is correct
31 Correct 481 ms 56056 KB Output is correct
32 Correct 641 ms 71744 KB Output is correct
33 Correct 1155 ms 108512 KB Output is correct
34 Correct 245 ms 37316 KB Output is correct
35 Correct 1090 ms 108316 KB Output is correct
36 Correct 1164 ms 108740 KB Output is correct
37 Correct 1101 ms 108740 KB Output is correct
38 Correct 1089 ms 108552 KB Output is correct
39 Correct 1022 ms 108528 KB Output is correct
40 Correct 976 ms 108484 KB Output is correct
41 Correct 1097 ms 108484 KB Output is correct
42 Correct 1012 ms 108736 KB Output is correct
43 Correct 652 ms 107732 KB Output is correct
44 Correct 708 ms 108100 KB Output is correct
45 Correct 658 ms 107764 KB Output is correct
46 Correct 479 ms 58056 KB Output is correct
47 Correct 408 ms 40944 KB Output is correct
48 Correct 577 ms 74156 KB Output is correct
49 Correct 601 ms 74336 KB Output is correct