oj.uz

Submission #953187

# Submission time Handle Problem Language Result Execution time Memory
953187 2024-03-25T16:25:16 Z underwaterkillerwhale Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 674 ms 77252 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 () {
    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]);
    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;

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() {
    cin >> n >> Q;
    rep (i, 1, n) {
        cin >> arr[i].a >> arr[i].b;
    }
    rep (i, 1, Q) {
        cin >> 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;
            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) {
        res += final_arr[i];
    }
    cout<<res <<"\n";
}

#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 Segment_Tree_helper1::update(int, int, int, int, int)':
fortune_telling2.cpp:72:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |         int mid = l + r >> 1;
      |                   ~~^~~
fortune_telling2.cpp: In member function 'int Segment_Tree_helper1::get(int, int, int, int, int, int)':
fortune_telling2.cpp:85:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |         int mid = l + r >> 1;
      |                   ~~^~~
fortune_telling2.cpp: In member function 'int Segment_Tree_helper1::walk_Left(int, int, int, int)':
fortune_telling2.cpp:94:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |         int mid = l + r >> 1;
      |                   ~~^~~
fortune_telling2.cpp: In member function 'int Segment_Tree_helper1::walk_Right(int, int, int, int)':
fortune_telling2.cpp:104:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  104 |         int mid = l + r >> 1;
      |                   ~~^~~
fortune_telling2.cpp: In member function 'int Segment_Tree_helper1::search_rightmost_pole(int, int, int, int)':
fortune_telling2.cpp:113:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  113 |         int mid = l + r >> 1;
      |                   ~~^~~
fortune_telling2.cpp: In function 'void solution()':
fortune_telling2.cpp:174:29: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  174 |             if (parity ^ ok & 1) final_arr[id] = nen[B - 1];
      |                          ~~~^~~

Subtask #1
4.0 / 4.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21340 KB Output is correct
2 Correct 5 ms 21492 KB Output is correct
3 Correct 6 ms 21596 KB Output is correct
4 Correct 5 ms 21596 KB Output is correct
5 Correct 6 ms 21596 KB Output is correct
6 Correct 5 ms 21604 KB Output is correct
7 Correct 4 ms 21552 KB Output is correct
8 Correct 5 ms 21592 KB Output is correct
9 Correct 4 ms 21596 KB Output is correct
10 Correct 5 ms 21340 KB Output is correct
11 Correct 4 ms 21552 KB Output is correct
12 Correct 5 ms 21340 KB Output is correct
13 Correct 4 ms 21340 KB Output is correct
14 Correct 27 ms 27748 KB Output is correct
15 Correct 48 ms 30000 KB Output is correct
16 Correct 72 ms 31952 KB Output is correct
17 Correct 98 ms 34388 KB Output is correct
18 Correct 96 ms 34260 KB Output is correct
19 Correct 99 ms 34384 KB Output is correct
20 Correct 101 ms 34224 KB Output is correct
21 Correct 94 ms 34260 KB Output is correct
22 Correct 84 ms 32328 KB Output is correct
23 Correct 82 ms 31160 KB Output is correct
24 Correct 82 ms 30428 KB Output is correct
25 Correct 83 ms 32724 KB Output is correct
26 Correct 82 ms 31900 KB Output is correct
27 Correct 90 ms 32468 KB Output is correct
28 Correct 86 ms 32464 KB Output is correct
29 Correct 99 ms 33188 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21340 KB Output is correct
2 Correct 5 ms 21492 KB Output is correct
3 Correct 6 ms 21596 KB Output is correct
4 Correct 5 ms 21596 KB Output is correct
5 Correct 6 ms 21596 KB Output is correct
6 Correct 5 ms 21604 KB Output is correct
7 Correct 4 ms 21552 KB Output is correct
8 Correct 5 ms 21592 KB Output is correct
9 Correct 4 ms 21596 KB Output is correct
10 Correct 5 ms 21340 KB Output is correct
11 Correct 4 ms 21552 KB Output is correct
12 Correct 5 ms 21340 KB Output is correct
13 Correct 4 ms 21340 KB Output is correct
14 Correct 27 ms 27748 KB Output is correct
15 Correct 48 ms 30000 KB Output is correct
16 Correct 72 ms 31952 KB Output is correct
17 Correct 98 ms 34388 KB Output is correct
18 Correct 96 ms 34260 KB Output is correct
19 Correct 99 ms 34384 KB Output is correct
20 Correct 101 ms 34224 KB Output is correct
21 Correct 94 ms 34260 KB Output is correct
22 Correct 84 ms 32328 KB Output is correct
23 Correct 82 ms 31160 KB Output is correct
24 Correct 82 ms 30428 KB Output is correct
25 Correct 83 ms 32724 KB Output is correct
26 Correct 82 ms 31900 KB Output is correct
27 Correct 90 ms 32468 KB Output is correct
28 Correct 86 ms 32464 KB Output is correct
29 Correct 99 ms 33188 KB Output is correct
30 Correct 415 ms 49580 KB Output is correct
31 Correct 477 ms 55060 KB Output is correct
32 Correct 523 ms 61908 KB Output is correct
33 Correct 654 ms 75644 KB Output is correct
34 Correct 403 ms 48204 KB Output is correct
35 Correct 666 ms 77048 KB Output is correct
36 Correct 672 ms 75456 KB Output is correct
37 Correct 674 ms 76120 KB Output is correct
38 Correct 668 ms 76828 KB Output is correct
39 Correct 662 ms 76952 KB Output is correct
40 Correct 614 ms 76736 KB Output is correct
41 Correct 655 ms 77048 KB Output is correct
42 Correct 666 ms 75964 KB Output is correct
43 Correct 518 ms 75968 KB Output is correct
44 Correct 506 ms 77252 KB Output is correct
45 Correct 510 ms 76720 KB Output is correct
46 Correct 519 ms 61372 KB Output is correct
47 Correct 506 ms 55232 KB Output is correct
48 Correct 555 ms 67624 KB Output is correct
49 Correct 531 ms 66164 KB Output is correct