Submission #988851

#	Time	Username	Problem	Language	Result	Execution time	Memory
988851		arpitpandey992	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	4 / 100	3068 ms	6612 KiB

fortune_telling2

const long long M = 1e9 + 7;
const int INF = 2147483647;
const long long INFLL = 9223372036854775807ll;
#pragma region Template Start
#include <algorithm>
#include <chrono>
#include <climits>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template <typename T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// template <typename T>
// using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
using tiii = tuple<int, int, int>;
using tlll = tuple<ll, ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vpii = vector<pii>;
using vpll = vector<pll>;
#define endl '\n'
#define nl cout << '\n'
#define pb push_back
#define pob pop_back
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define FIX(number, digits) fixed << setprecision(digits) << number  // use in cout
#define fok(i, k, n) for (ll i = k; i < n; i++)
#define Fok(i, k, n) for (ll i = n; i >= k; i--)
#define fo(i, n) for (ll i = 0; i < n; i++)
#define Fo(i, n) for (ll i = n; i >= 0; i--)
#define CHK(s, k) (s.find(k) != s.end())
#define all(v) v.begin(), v.end()
#define allg(v) v.rbegin(), v.rend()
#define Sort(v) sort(all(v))
#define Sortg(v) sort(allg(v))
#define sz(v) (static_cast<ll>(v.size()))
#define bs(v, val) binary_search(all(v), val)
#define lb(v, val) lower_bound(all(v), val)
#define ub(v, val) upper_bound(all(v), val)
#define setbits(x) __builtin_popcount(x)
#define start_clock() auto start_time = std::chrono::high_resolution_clock::now()
#define measure()                                              \
    auto end_time = std::chrono::high_resolution_clock::now(); \
    cerr << (end_time - start_time) / std::chrono::milliseconds(1) << "ms" << endl

#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define fileio                        \
    freopen("input.txt", "r", stdin); \
    freopen("output.txt", "w", stdout)

#pragma endregion Template End

class RangeCountHelper {
   public:
    RangeCountHelper(ll n) {
        this->n = n;
        this->st.resize(4 * n, 0);
        this->imaginaryArray.resize(n, 0);
    }

    ll getCount(ll l, ll r) {
        return this->_query(l, r, 0, n - 1, 0);
    }

    void switchOn(ll index) {
        imaginaryArray[index] = 1;
        this->_update(index, 0, n - 1, 0);
    }

   private:
    vector<ll> st;
    vector<ll> imaginaryArray;
    ll n;

    ll _query(ll l, ll r, ll sl, ll sr, ll idx) {
        if (l > sr || r < sl || sl > sr)
            return 0;
        if (sl >= l && sr <= r)
            return st[idx];
        ll mid = (sl + sr) / 2;
        return _query(l, r, sl, mid, idx * 2 + 1) + _query(l, r, mid + 1, sr, idx * 2 + 2);
    }

    ll _update(ll i, ll sl, ll sr, ll idx) {
        if (i > sr || i < sl)
            return st[idx];
        if (sl == sr) {
            return st[idx] = imaginaryArray[i];
        }
        ll mid = (sl + sr) / 2;
        return st[idx] = _update(i, sl, mid, idx * 2 + 1) + _update(i, mid + 1, sr, idx * 2 + 2);
    }
};

class LargestIndexHelper {
   public:
    LargestIndexHelper(vector<ll> &a) {
        this->n = a.size();
        this->a = a;
        this->st.resize(4 * n, 0);
        this->_build(0, n - 1, 0);
    }

    ll getLargestIndex(ll greaterThanEqualTo) {
        return _query(greaterThanEqualTo, 0, n - 1, 0);
    }

    void invalidate(ll index) {
        this->_remove(index, 0, n - 1, 0);
    }

   private:
    vector<ll> st;
    vector<ll> a;
    ll n;

    ll _query(ll k, ll sl, ll sr, ll idx) {
        if (sl == sr) {
            return a[sl] >= k ? sl : -1;
        }
        if (a[st[idx]] >= k)
            return st[idx];
        int mid = (sl + sr) / 2;
        return max(_query(k, sl, mid, idx * 2 + 1), _query(k, mid + 1, sr, idx * 2 + 2));
    }

    ll _remove(ll i, ll sl, ll sr, ll idx) {
        if (i > sr || i < sl)
            return st[idx];
        if (sl == sr) {
            a[i] = -INF;
            return st[idx] = i;  // remains unchanged
        }
        ll mid = (sl + sr) / 2;
        ll left = _remove(i, sl, mid, idx * 2 + 1);
        ll right = _remove(i, mid + 1, sr, idx * 2 + 2);
        return st[idx] = max(left, right);
    }

    ll _build(ll sl, ll sr, ll idx) {
        if (sl == sr) {
            return st[idx] = sl;
        }
        ll mid = (sl + sr) / 2;
        ll left = _build(sl, mid, idx * 2 + 1);
        ll right = _build(mid + 1, sr, idx * 2 + 2);
        return st[idx] = max(left, right);
    }
};

void solve() {
    ll n, k;
    cin >> n >> k;
    vector<pair<ll, ll>> a(n);
    vector<ll> queries(k);
    fo(i, n) {
        cin >> a[i].first >> a[i].second;
    }
    sort(a.begin(), a.end(), [](auto &p1, auto &p2) { return max(p1.ff, p1.ss) > max(p2.ff, p2.ss); });
    fo(i, k) {
        cin >> queries[i];
    }
    RangeCountHelper rangeCountHelper(queries.size());
    LargestIndexHelper largestIndexHelper(queries);
    priority_queue<pair<ll, ll>> q;
    for (ll i = 0; i < k; i++) {
        q.push({queries[i], i});
    }
    ll ans = 0;
    for (auto &[ai, bi] : a) {
        // for (int i = 1; i <= *max_element(all(queries)); i++) {
        //     cout << "greater than " << i << " -> " << largestIndexHelper.getLargestIndex(i) << endl;
        // }
        while (q.size() && q.top().ff >= max(ai, bi)) {
            auto [currentMaxQuery, currentMaxQueryIndex] = q.top();
            q.pop();
            rangeCountHelper.switchOn(currentMaxQueryIndex);
            largestIndexHelper.invalidate(currentMaxQueryIndex);
        }
        ll largestIndex = largestIndexHelper.getLargestIndex(min(ai, bi));
        ll rotationCount = rangeCountHelper.getCount(largestIndex + 1, k - 1);
        bool isRotated = rotationCount % 2 == 1;
        if (ai < bi) {
            if (largestIndex != -1)
                isRotated = !isRotated;
        }
        ans += isRotated ? bi : ai;
    }
    cout << ans << endl;
}

int main() {
#ifdef ONLINE_JUDGE
    fastio;
#endif
    ll tes = 1;
    // cin >> tes;
    for (ll t = 1; t <= tes; t++) {
        // cout << "Case #" << t << ": ";
        solve();
    }
}
/*
    What to do?
    1. for any query q[i] >= a[i].ss && q[i] < a[i].ff (assuming first > second)
        - This will cause rotation to revert back to initial state (above assumption)
        - After last q[i] >= ... && q[i] < ..., all q[i] >= a[i].ff will rotate once
    2. find the last query index whose value is lesser than a[i].ff but >= a[i].ss
        - max index in array whose value is >= given value [queries]
        - since we are iterating in reducing value of a[i].ff, we can permanently ignore them when calculating maxIndex
        - basically largest index with value >= given query
    3. rotationCount = number of q[i] where i > above index && q[i] >= a[i].ff
        - willRotate = rotationCount%2 == 1
        - if a[i].ff < a[i].ss:
            - rotation will still count in the same way, just that we assume we start from bigger value as first
            - if no query between a[i].ff and a[i].ss, then rotation will count from smaller value (edge case).
    4. when iterating in reverse manner of a[i].ff, the above count will only increase
        - simple range sum query in binary array
        - initially, all zero
        - while iterating on a, make imaginaryArray[j] = 1 where q[j] >= a[i].ff
*/

Compilation message (stderr)

fortune_telling2.cpp:4: warning: ignoring '#pragma region Template' [-Wunknown-pragmas]
    4 | #pragma region Template Start
      | 
fortune_telling2.cpp:87: warning: ignoring '#pragma endregion Template' [-Wunknown-pragmas]
   87 | #pragma endregion Template End
      |

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