oj.uz

답안 #988968

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
988968 2024-05-27T06:35:00 Z MamaShakuni 운세 보기 2 (JOI14_fortune_telling2) C++17
100 / 100
 169 ms 17872 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
 
//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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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