oj.uz

Submission #953183

# Submission time Handle Problem Language Result Execution time Memory
953183 2024-03-25T16:19:12 Z underwaterkillerwhale Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 1151 ms 85216 KB 
#include <bits/stdc++.h>
#define se          second
#define fs          first
#define pb          push_back
#define ll          long long
#define ii          pair<ll,ll>
#define ld          long double
#define SZ(v)       (int)v.size()
#define ALL(v)      v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for (auto id : v)
#define rep(i,m,n)  for(int i=(m); i<=(n); i++)
#define reb(i,m,n)  for(int i=(m); i>=(n); i--)

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }


const int N = 2e5 + 7;
const int Mod = 1e9 + 7;
const int szBL = 500;
const int INF = 2e9 + 7;
const int BASE = 137;

struct Arr_Data {
    int a, b;
    bool isswapped;
    Arr_Data () : a(0), b(0), isswapped(0) {};
};

///input:
int n, Q;
Arr_Data arr[N];
int qr[N];

///compress:
int num_Val;
vector<int> nen;

int CPR (int X) {
    return lower_bound(ALL(nen), X) - nen.begin() + 1;
}

void compress () {
    sort (ALL(nen));
    nen.resize(num_Val = unique(ALL(nen)) - nen.begin());
    rep (i, 1, n) {
        arr[i].a = CPR(arr[i].a);
        arr[i].b = CPR(arr[i].b);
    }
    rep (i, 1, Q) qr[i] = CPR(qr[i]);
}

///data:
vector<vector<int>> queries, events;

namespace sub3 {
    class Segment_Tree_helper1 {
    private:
        int Range;
        int st[3][N << 2];
        void update (int id, int l, int r, int pos, int val) {
            if (l > pos || r < pos) return;
            if (l == r) {
                st[1][id] = st[0][id] = st[2][id] = val;
                return;
            }
            int mid = l + r >> 1;
            update (id << 1, l, mid, pos, val);
            update (id << 1 | 1, mid + 1, r, pos, val);
            st[0][id] = min(st[0][id << 1], st[0][id << 1 | 1]);
            st[1][id] = max(st[1][id << 1], st[1][id << 1 | 1]);
            st[2][id] = st[2][id << 1] + st[2][id << 1 | 1];
        }
        int get (int id, int l, int r, int u, int v, int typ) {
            if (l > v || r < u) {
                if (typ == 0) return INF;
                else return 0;
            }
            if (l >= u && r <= v) return st[typ][id];
            int mid = l + r >> 1;
            if (typ == 1) return max(get (id << 1, l, mid, u, v, typ), get (id << 1 | 1, mid + 1, r, u, v, typ));
            else if (typ == 0) return min(get (id << 1, l, mid, u, v, typ), get (id << 1 | 1, mid + 1, r, u, v, typ));
            else return get (id << 1, l, mid, u, v, typ) + get (id << 1 | 1, mid + 1, r, u, v, typ);
        }
        int walk_Left (int id, int l, int r, int bound) { ///walk to Find L when the upper_bound is bound
            if (l > bound) return -1;
            if (st[1][id] == 0) return -1;
            if (l == r) return l;
            int mid = l + r >> 1;
            int res = -1;
            if (mid + 1 <= bound) res = walk_Left (id << 1 | 1 , mid + 1, r, bound);
            if (res == -1) res = walk_Left (id << 1, l, mid, bound);
            return res;
        }
        int walk_Right (int id, int l, int r, int bound) {  ///walk to Find R when the lower_bound is bound
            if (r < bound) return -1;
            if (st[1][id] == 0) return -1;
            if (l == r) return l;
            int mid = l + r >> 1;
            int res = -1;
            if (mid >= bound) res = walk_Right (id << 1, l, mid, bound);
            if (res == -1) res = walk_Right (id << 1 | 1, mid + 1, r, bound);
            return res;
        }
        int search_rightmost_pole (int id, int l, int r, int bound) {
            if (st[1][id] < bound) return -1;
            if (l == r) return l;
            int mid = l + r >> 1;
            int res = -1;
            if (st[1][id << 1 | 1] >= bound) res = search_rightmost_pole (id << 1 | 1, mid + 1, r, bound);
            if (res == -1) res = search_rightmost_pole (id << 1, l, mid, bound);
            return res;
        }

    public:
        void init(int n ) {
            Range = n;
            rep (i, 0, (Range + 1) << 2) st[0][i] = INF, st[1][i] = 0, st[0][i] = 0;
        }
        void update (int pos, int val) { update (1, 0, Range, pos, val); }
        int getMx (int L, int R) { return get (1, 0, Range, L, R, 1); }
        int getMn (int L, int R) { return get (1, 0, Range, L, R, 0);}
        int Sum (int L, int R) { return get (1, 0, Range, L, R, 2); }
        int walk_Left (int bound){ return walk_Left (1, 0, Range, bound); }
        int walk_Right (int bound) { return walk_Right (1, 0, Range, bound); }
        int search_rightmost_pole (int bound) { return search_rightmost_pole (1, 0, Range, bound); }

    }ST, Partition, values_Range;

    void solution() {
        nen = {0, INF};
        rep (i, 1, n) nen.push_back(arr[i].a), nen.push_back(arr[i].b);
        rep (i, 1, Q) nen.push_back(qr[i]);

        compress();

        events.resize(num_Val + 1, vector<int> (0)), queries.resize(num_Val + 1, vector<int> (0));
        rep (i, 1, n) {
            if (arr[i].a > arr[i].b) {
                swap(arr[i].a, arr[i].b);
                arr[i].isswapped = 1;
            }
            events[arr[i].b].push_back(i);
        }
        rep (i, 1, Q) queries[qr[i]].push_back(i);

        ST.init(Q), Partition.init(Q), values_Range.init(Q + 1);
        rep (i, 1, Q) ST.update(i, qr[i]);
        values_Range.update (Q + 1, ST.getMx(1, Q));
        vector<int> final_arr(n + 1, 0);
        reb (X, num_Val, 1) {
            iter (&id, queries[X]) {
                int boundL = Partition.walk_Left(id - 1), boundR = Partition.walk_Right(id + 1);
                if (boundL == -1) boundL = 0;
                if (boundR == -1) boundR = Q + 1;
                Partition.update (id, 1);
                values_Range.update (id, ST.getMx(boundL + 1, id - 1));
                values_Range.update (boundR, ST.getMx(id + 1, boundR - 1));
            }
            iter (&id, events[X]) {
                int A = arr[id].a, B = arr[id].b, swapped = arr[id].isswapped;
                int rightmost = values_Range.search_rightmost_pole(A);
                bool ok = rightmost == -1 ? swapped : 0;
                if (rightmost == -1) rightmost = 0;
//                cout << id << " "<<rightmost<<"\n";
                int parity = Partition.Sum (rightmost + 1, Q) & 1;
                if (parity ^ ok & 1) final_arr[id] = nen[B - 1];
                else {
                    if (values_Range.getMx(Q + 1, Q + 1) >= A) final_arr[id] = nen[B - 1];
                    else final_arr[id] = nen[A - 1];
                }
            }
        }
        ll res = 0;
        rep (i, 1, n) {
            cerr << final_arr[i] << " ";
            res += final_arr[i];
        }
        cout<<res <<"\n";
    }
}
void solution() {
    cin >> n >> Q;
    rep (i, 1, n) {
        cin >> arr[i].a >> arr[i].b;
    }
    rep (i, 1, Q) {
        cin >> qr[i];
    }
    sub3 :: solution();
}

#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);

int main() {
//    file("c");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll num_Test = 1;
//    cin >> num_Test;
    while(num_Test--)
        solution();
}
/*


*/

Compilation message

fortune_telling2.cpp: In member function 'void sub3::Segment_Tree_helper1::update(int, int, int, int, int)':
fortune_telling2.cpp:70:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |             int mid = l + r >> 1;
      |                       ~~^~~
fortune_telling2.cpp: In member function 'int sub3::Segment_Tree_helper1::get(int, int, int, int, int, int)':
fortune_telling2.cpp:83:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |             int mid = l + r >> 1;
      |                       ~~^~~
fortune_telling2.cpp: In member function 'int sub3::Segment_Tree_helper1::walk_Left(int, int, int, int)':
fortune_telling2.cpp:92:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |             int mid = l + r >> 1;
      |                       ~~^~~
fortune_telling2.cpp: In member function 'int sub3::Segment_Tree_helper1::walk_Right(int, int, int, int)':
fortune_telling2.cpp:102:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |             int mid = l + r >> 1;
      |                       ~~^~~
fortune_telling2.cpp: In member function 'int sub3::Segment_Tree_helper1::search_rightmost_pole(int, int, int, int)':
fortune_telling2.cpp:111:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  111 |             int mid = l + r >> 1;
      |                       ~~^~~
fortune_telling2.cpp: In function 'void sub3::solution()':
fortune_telling2.cpp:170:33: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  170 |                 if (parity ^ ok & 1) final_arr[id] = nen[B - 1];
      |                              ~~~^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21336 KB Output is correct
2 Correct 5 ms 21340 KB Output is correct
3 Correct 7 ms 21648 KB Output is correct
4 Correct 7 ms 21596 KB Output is correct
5 Correct 7 ms 21592 KB Output is correct
6 Correct 7 ms 21596 KB Output is correct
7 Correct 7 ms 21596 KB Output is correct
8 Correct 7 ms 21592 KB Output is correct
9 Correct 7 ms 21596 KB Output is correct
10 Correct 7 ms 21340 KB Output is correct
11 Correct 8 ms 21596 KB Output is correct
12 Correct 7 ms 21592 KB Output is correct
13 Correct 7 ms 21612 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21336 KB Output is correct
2 Correct 5 ms 21340 KB Output is correct
3 Correct 7 ms 21648 KB Output is correct
4 Correct 7 ms 21596 KB Output is correct
5 Correct 7 ms 21592 KB Output is correct
6 Correct 7 ms 21596 KB Output is correct
7 Correct 7 ms 21596 KB Output is correct
8 Correct 7 ms 21592 KB Output is correct
9 Correct 7 ms 21596 KB Output is correct
10 Correct 7 ms 21340 KB Output is correct
11 Correct 8 ms 21596 KB Output is correct
12 Correct 7 ms 21592 KB Output is correct
13 Correct 7 ms 21612 KB Output is correct
14 Correct 46 ms 28128 KB Output is correct
15 Correct 91 ms 30580 KB Output is correct
16 Correct 142 ms 33576 KB Output is correct
17 Correct 186 ms 35792 KB Output is correct
18 Correct 187 ms 35908 KB Output is correct
19 Correct 193 ms 35812 KB Output is correct
20 Correct 190 ms 35788 KB Output is correct
21 Correct 183 ms 35796 KB Output is correct
22 Correct 177 ms 32968 KB Output is correct
23 Correct 167 ms 31952 KB Output is correct
24 Correct 169 ms 31188 KB Output is correct
25 Correct 179 ms 33748 KB Output is correct
26 Correct 156 ms 33232 KB Output is correct
27 Correct 183 ms 33912 KB Output is correct
28 Correct 175 ms 33840 KB Output is correct
29 Correct 197 ms 35456 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21336 KB Output is correct
2 Correct 5 ms 21340 KB Output is correct
3 Correct 7 ms 21648 KB Output is correct
4 Correct 7 ms 21596 KB Output is correct
5 Correct 7 ms 21592 KB Output is correct
6 Correct 7 ms 21596 KB Output is correct
7 Correct 7 ms 21596 KB Output is correct
8 Correct 7 ms 21592 KB Output is correct
9 Correct 7 ms 21596 KB Output is correct
10 Correct 7 ms 21340 KB Output is correct
11 Correct 8 ms 21596 KB Output is correct
12 Correct 7 ms 21592 KB Output is correct
13 Correct 7 ms 21612 KB Output is correct
14 Correct 46 ms 28128 KB Output is correct
15 Correct 91 ms 30580 KB Output is correct
16 Correct 142 ms 33576 KB Output is correct
17 Correct 186 ms 35792 KB Output is correct
18 Correct 187 ms 35908 KB Output is correct
19 Correct 193 ms 35812 KB Output is correct
20 Correct 190 ms 35788 KB Output is correct
21 Correct 183 ms 35796 KB Output is correct
22 Correct 177 ms 32968 KB Output is correct
23 Correct 167 ms 31952 KB Output is correct
24 Correct 169 ms 31188 KB Output is correct
25 Correct 179 ms 33748 KB Output is correct
26 Correct 156 ms 33232 KB Output is correct
27 Correct 183 ms 33912 KB Output is correct
28 Correct 175 ms 33840 KB Output is correct
29 Correct 197 ms 35456 KB Output is correct
30 Correct 434 ms 51664 KB Output is correct
31 Correct 568 ms 58212 KB Output is correct
32 Correct 746 ms 66760 KB Output is correct
33 Correct 1132 ms 84324 KB Output is correct
34 Correct 403 ms 50304 KB Output is correct
35 Correct 1118 ms 85036 KB Output is correct
36 Correct 1111 ms 85076 KB Output is correct
37 Correct 1151 ms 83588 KB Output is correct
38 Correct 1106 ms 85216 KB Output is correct
39 Correct 1118 ms 84168 KB Output is correct
40 Correct 1058 ms 84876 KB Output is correct
41 Correct 1126 ms 83360 KB Output is correct
42 Correct 1100 ms 84584 KB Output is correct
43 Correct 963 ms 82568 KB Output is correct
44 Correct 944 ms 83108 KB Output is correct
45 Correct 952 ms 83780 KB Output is correct
46 Correct 964 ms 66424 KB Output is correct
47 Correct 931 ms 60464 KB Output is correct
48 Correct 1018 ms 73924 KB Output is correct
49 Correct 1004 ms 74200 KB Output is correct