oj.uz

Submission #988859

# Submission time Handle Problem Language Result Execution time Memory
988859 2024-05-26T13:30:11 Z arpitpandey992 Fortune Telling 2 (JOI14_fortune_telling2) C++17
4 / 100
 3000 ms 4228 KB 
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(int n) {
        this->n = n;
        this->st.resize(4 * n, 0);
        this->imaginaryArray.resize(n, 0);
    }

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

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

   private:
    vector<int> st;
    vector<int> imaginaryArray;
    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);
    }

    int _update(int i, int sl, int sr, int idx) {
        if (i > sr || i < sl)
            return st[idx];
        if (sl == sr) {
            return st[idx] = imaginaryArray[i];
        }
        int mid = (sl + sr) / 2;
        if (i <= mid)
            _update(i, sl, mid, idx * 2 + 1);
        else
            _update(i, mid + 1, sr, idx * 2 + 2);
        return 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 (sl == sr) {
            return a[sl] >= k ? sl : -1;
        }
        if (a[st[idx]] >= k)
            return st[idx];
        int mid = (sl + sr) / 2;
        int right = _query(k, mid + 1, sr, idx * 2 + 2);
        if (right != -1)
            return right;
        return _query(k, sl, mid, idx * 2 + 1);
    }

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

    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(left, right);
    }
};

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);
    priority_queue<pair<int, int>> q;
    for (int i = 0; i < k; i++) {
        q.push({queries[i], i});
    }
    ll ans = 0;
    for (auto &[ai, bi] : a) {
        while (q.size() && q.top().ff >= max(ai, bi)) {
            auto [currentMaxQuery, currentMaxQueryIndex] = q.top();
            q.pop();
            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() {
#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

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 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 472 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 472 KB Output is correct
8 Correct 1 ms 476 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 3 ms 536 KB Output is correct
12 Correct 3 ms 348 KB Output is correct
13 Correct 3 ms 444 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 472 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 472 KB Output is correct
8 Correct 1 ms 476 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 3 ms 536 KB Output is correct
12 Correct 3 ms 348 KB Output is correct
13 Correct 3 ms 444 KB Output is correct
14 Correct 12 ms 1372 KB Output is correct
15 Correct 24 ms 2396 KB Output is correct
16 Correct 38 ms 3208 KB Output is correct
17 Correct 50 ms 4044 KB Output is correct
18 Correct 50 ms 4228 KB Output is correct
19 Correct 56 ms 4048 KB Output is correct
20 Correct 57 ms 4048 KB Output is correct
21 Correct 36 ms 4052 KB Output is correct
22 Correct 29 ms 3796 KB Output is correct
23 Correct 32 ms 3800 KB Output is correct
24 Correct 36 ms 3800 KB Output is correct
25 Correct 26 ms 3800 KB Output is correct
26 Correct 1537 ms 4044 KB Output is correct
27 Correct 1824 ms 4048 KB Output is correct
28 Correct 1768 ms 4048 KB Output is correct
29 Execution timed out 3071 ms 4048 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 472 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 472 KB Output is correct
8 Correct 1 ms 476 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 3 ms 536 KB Output is correct
12 Correct 3 ms 348 KB Output is correct
13 Correct 3 ms 444 KB Output is correct
14 Correct 12 ms 1372 KB Output is correct
15 Correct 24 ms 2396 KB Output is correct
16 Correct 38 ms 3208 KB Output is correct
17 Correct 50 ms 4044 KB Output is correct
18 Correct 50 ms 4228 KB Output is correct
19 Correct 56 ms 4048 KB Output is correct
20 Correct 57 ms 4048 KB Output is correct
21 Correct 36 ms 4052 KB Output is correct
22 Correct 29 ms 3796 KB Output is correct
23 Correct 32 ms 3800 KB Output is correct
24 Correct 36 ms 3800 KB Output is correct
25 Correct 26 ms 3800 KB Output is correct
26 Correct 1537 ms 4044 KB Output is correct
27 Correct 1824 ms 4048 KB Output is correct
28 Correct 1768 ms 4048 KB Output is correct
29 Execution timed out 3071 ms 4048 KB Time limit exceeded
30 Halted 0 ms 0 KB -