Submission #988968

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
988968	2024-05-27T06:35:00 Z	MamaShakuni	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	169 ms	17872 KB

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
 
//This code-submission is to address the noob-ly mistakes made by arpitpandey992 in his implementation... Don't worry son, CP not meant for everyone

class RangeCountHelper {
   public:
    RangeCountHelper(int n) {
        this->n = n;
        this->st.resize(4 * n, 0);
    }
 
    int getCount(int l, int r) {
        return this->_query(l, r, 0, n - 1, 0);
    }
 
    void switchOn(int index) {
        this->_update(index, 0, n - 1, 0);
    }
 
   private:
    vector<int> st;
    int n;
 
    int _query(int l, int r, int sl, int sr, int idx) {
        if (l > sr || r < sl || sl > sr)
            return 0;
        if (sl >= l && sr <= r)
            return st[idx];
        int mid = (sl + sr) / 2;
        return _query(l, r, sl, mid, idx * 2 + 1) + _query(l, r, mid + 1, sr, idx * 2 + 2);
    }
 
    void _update(int i, int sl, int sr, int idx) {
        if (i > sr || i < sl)
            return;
        if (sl == sr) {
            st[idx] = 1;
            return;
        }
        int mid = (sl + sr) / 2;
        if (i <= mid)
            _update(i, sl, mid, idx * 2 + 1);
        else
            _update(i, mid + 1, sr, idx * 2 + 2);
        st[idx] = st[idx * 2 + 1] + st[idx * 2 + 2];
    }
};
 
class LargestIndexHelper {
   public:
    LargestIndexHelper(vector<int> &a) {
        this->n = a.size();
        this->a = a;
        this->st.resize(4 * n, 0);
        this->_build(0, n - 1, 0);
    }
 
    int getLargestIndex(int greaterThanEqualTo) {
        return _query(greaterThanEqualTo, 0, n - 1, 0);
    }
 
    void invalidate(int index) {
        this->_remove(index, 0, n - 1, 0);
    }
 
   private:
    vector<int> st;
    vector<int> a;
    int n;
 
    int _query(int k, int sl, int sr, int idx) {
        if (a[st[idx]] < k)
            return -1;
        if (sl == sr) 
            return sl;
        
        int mid = (sl + sr) / 2;
        //We are not Rishi Sethia, we do not write nested ifs
        int ans = (a[st[2*idx+2]] >= k) ? _query(k, mid + 1, sr, idx * 2 + 2) : _query(k, sl, mid, idx * 2 + 1);
        //arpitpandey992 => Not the best IITR-EE has to offer
        //Intelligent traversal of segmentTrees are meant for intelligent people I guess :)
        return ans;
    }
 
    void _remove(int i, int sl, int sr, int idx) {
        if (i > sr || i < sl)
            return;
        if (sl == sr) {
            a[i] = -1;     // this will no longer be considered during query
            st[idx] = sl;  // Maximum value between sl and sr (=sl) is still stored in sl
            return;
        }
        int mid = (sl + sr) / 2;
        if (i <= mid)
            _remove(i, sl, mid, idx * 2 + 1);
        else
            _remove(i, mid + 1, sr, idx * 2 + 2);
        int left = st[2*idx+1], right = st[2*idx+2];
        st[idx] = (max(a[left], a[right]) == a[right]) ? right : left;
    }
 
    int _build(int sl, int sr, int idx) {
        if (sl == sr) {
            return st[idx] = sl;
        }
        int mid = (sl + sr) / 2;
        int left = _build(sl, mid, idx * 2 + 1);
        int right = _build(mid + 1, sr, idx * 2 + 2);
        return st[idx] = (max(a[left], a[right]) == a[right]) ? right : left;
    }
};
 
void solve() {
    int n, k;
    cin >> n >> k;
    vector<pair<int, int>> a(n);
    vector<int> 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);
    vector<pair<int, int>> q;
    for (int i = 0; i < k; i++) {
        q.push_back({queries[i], i});
    }
    sort(q.begin(), q.end());
    ll ans = 0;
    for (auto &[ai, bi] : a) {
        while (q.size() && q.back().ff >= max(ai, bi)) {
            auto [currentMaxQuery, currentMaxQueryIndex] = q.back();
            q.pop_back();
            rangeCountHelper.switchOn(currentMaxQueryIndex);
            largestIndexHelper.invalidate(currentMaxQueryIndex);
        }
        int largestIndex = largestIndexHelper.getLargestIndex(min(ai, bi));
        int rotationCount = rangeCountHelper.getCount(largestIndex + 1, k - 1);
        bool isRotated = rotationCount % 2 == 1;
        if (ai < bi) {
            if (largestIndex != -1)
                isRotated = !isRotated;
        }
        ans += isRotated ? (ll)bi : (ll)ai;
    }
    cout << ans << endl;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    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

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.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	496 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	488 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct

Subtask #2

31.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	496 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	488 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	7 ms	1372 KB	Output is correct
15	Correct	15 ms	2264 KB	Output is correct
16	Correct	22 ms	3108 KB	Output is correct
17	Correct	30 ms	4064 KB	Output is correct
18	Correct	28 ms	4040 KB	Output is correct
19	Correct	25 ms	4060 KB	Output is correct
20	Correct	30 ms	4064 KB	Output is correct
21	Correct	18 ms	4064 KB	Output is correct
22	Correct	19 ms	3552 KB	Output is correct
23	Correct	20 ms	3548 KB	Output is correct
24	Correct	24 ms	3552 KB	Output is correct
25	Correct	16 ms	3552 KB	Output is correct
26	Correct	32 ms	3820 KB	Output is correct
27	Correct	32 ms	4060 KB	Output is correct
28	Correct	27 ms	4064 KB	Output is correct
29	Correct	28 ms	4136 KB	Output is correct

Subtask #3

65.0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	496 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	488 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	7 ms	1372 KB	Output is correct
15	Correct	15 ms	2264 KB	Output is correct
16	Correct	22 ms	3108 KB	Output is correct
17	Correct	30 ms	4064 KB	Output is correct
18	Correct	28 ms	4040 KB	Output is correct
19	Correct	25 ms	4060 KB	Output is correct
20	Correct	30 ms	4064 KB	Output is correct
21	Correct	18 ms	4064 KB	Output is correct
22	Correct	19 ms	3552 KB	Output is correct
23	Correct	20 ms	3548 KB	Output is correct
24	Correct	24 ms	3552 KB	Output is correct
25	Correct	16 ms	3552 KB	Output is correct
26	Correct	32 ms	3820 KB	Output is correct
27	Correct	32 ms	4060 KB	Output is correct
28	Correct	27 ms	4064 KB	Output is correct
29	Correct	28 ms	4136 KB	Output is correct
30	Correct	103 ms	12496 KB	Output is correct
31	Correct	112 ms	13760 KB	Output is correct
32	Correct	128 ms	14948 KB	Output is correct
33	Correct	158 ms	17624 KB	Output is correct
34	Correct	45 ms	12248 KB	Output is correct
35	Correct	169 ms	17616 KB	Output is correct
36	Correct	155 ms	17616 KB	Output is correct
37	Correct	159 ms	17616 KB	Output is correct
38	Correct	143 ms	17616 KB	Output is correct
39	Correct	157 ms	17752 KB	Output is correct
40	Correct	88 ms	17616 KB	Output is correct
41	Correct	148 ms	17868 KB	Output is correct
42	Correct	164 ms	17736 KB	Output is correct
43	Correct	65 ms	17104 KB	Output is correct
44	Correct	65 ms	17000 KB	Output is correct
45	Correct	66 ms	17008 KB	Output is correct
46	Correct	112 ms	15824 KB	Output is correct
47	Correct	146 ms	15692 KB	Output is correct
48	Correct	149 ms	17872 KB	Output is correct
49	Correct	149 ms	17768 KB	Output is correct