Submission #1253329

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253329		quangminh412	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	180 ms	11592 KiB

fortune_telling2

/*
  Ben Watson
  Handle codeforces : quangminh98

  Current Theme: Transformers !!!!
*/

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const string name = "test";

void solve();
signed main()
{
    if (fopen((name + ".inp").c_str(), "r"))
    {
        freopen((name + ".inp").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();

    return 0;
}

// main program
const int maxn = 2e5 + 1;

struct SegmentTree
{
    vector<int> st;
    int n;

    SegmentTree(int n) : n(n) { st.resize(4 * n + 1, 0); }

    void update(int head, int l, int r, int pos, int val)
    {
        if (pos < l || r < pos) return;
        if (l == r)
        {
            st[head] = val;
            return;
        }

        int mid = l + r >> 1;
        if (pos <= mid)
            update(head << 1, l, mid, pos, val);
        else
            update(head << 1 | 1, mid + 1, r, pos, val);
        st[head] = max(st[head << 1], st[head << 1 | 1]);
    }
    void update(int pos, int val) { update(1, 1, n, pos, val); }

    int query(int head, int l, int r, int u, int v)
    {
        if (l > v || r < u) return 0;
        if (u <= l && r <= v) return st[head];

        int mid = l + r >> 1;
        return max(query(head << 1, l, mid, u, v), query(head << 1 | 1, mid + 1, r, u, v));
    }
    int query(int u, int v) { return query(1, 1, n, u, v); }
};

struct FenwickTree
{
    vector<int> bits;
    int n;

    FenwickTree(int n) : n(n) { bits.resize(n + 1, 0); }

    void update(int pos, int val)
    {
        for (; pos <= n; pos += (pos & (-pos)))
            bits[pos] += val;
    }

    int query(int pos)
    {
        int res = 0;
        for (; pos > 0; pos -= (pos & (-pos)))
            res += bits[pos];
        return res;
    }
    int query(int l, int r) { return query(r) - query(l - 1); }
};

int n, k;
int a[maxn], b[maxn], T[maxn];
vector<pair<int, int>> cards, ops;

// compression
int cur;
int id[maxn];
vector<int> v;

void solve()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i] >> b[i];
        cards.push_back({max(a[i], b[i]), i});
    }
    for (int i = 1; i <= k; i++)
    {
        cin >> T[i];
        ops.push_back({T[i], i});
    }

    sort(cards.begin(), cards.end(), greater<pair<int, int>>());
    sort(ops.begin(), ops.end());

    // compression
    cur = 0;
    v.push_back(0);
    for (pair<int, int> it : ops)
    {
        int idx = it.second, val = it.first;
        v.push_back(val);
        id[idx] = ++cur;
    }
    reverse(ops.begin(), ops.end());

    SegmentTree st(k);
    FenwickTree bit(k);
    for (int i = 1; i <= k; i++)
        st.update(id[i], i);

    ll res = 0;
    int pos = 0;
    for (pair<int, int> it : cards)
    {
        int mx = it.first, i = it.second;

        while (pos < k && ops[pos].first >= mx)
        {
            int idx = ops[pos].second;
            pos++;

            st.update(id[idx], 0);
            bit.update(idx, 1);
        }

        int mn = min(a[i], b[i]);
        int Q = lower_bound(v.begin() + 1, v.end(), mn) - v.begin();
        if (Q == k + 1)
        {
            int num = bit.query(1, k);
            res += ((num % 2 == 0) ? a[i] : b[i]);
        } else
        {
            int index = st.query(Q, k);
            int num = (index == k ? 0 : bit.query(index + 1, k));
            if (index == 0)
                res += (num % 2 == 0 ? a[i] : b[i]);
            else
                res += (num % 2 == 0 ? (mx == a[i] ? a[i] : b[i]) : (mx == a[i] ? b[i] : a[i]));
        }
    }

    cout << res << '\n';
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen((name + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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