oj.uz

Submission #952995

# Submission time Handle Problem Language Result Execution time Memory
952995 2024-03-25T09:37:23 Z underwaterkillerwhale Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 1662 ms 82956 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 if (typ == 2) 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;
        }

    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); }

    }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();
//        num_Val = 10;

        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)); ///dont need to consider the edgecase
                values_Range.update (boundR, ST.getMx(id + 1, boundR - 1));
//                cerr << "update: "<<id<<" "<<boundL<< " "<<ST.getMx(boundL + 1, id - 1)<<"\n";
            }
            iter (&id, events[X]) {
                int A = arr[id].a, B = arr[id].b, swapped = arr[id].isswapped;
                int Lf = 0, Rt = Q;
                while (Lf < Rt) {
                    int mid = Lf + Rt + 1 >> 1;
                    if (values_Range.getMx(mid, Q) >= A) Lf = mid;
                    else Rt = mid - 1;
                }
                if (values_Range.getMx(Lf, Q) < A) {
                    int parity = Partition.Sum(1, Q);
//                    cerr << id <<"hihi\n";
                    /// a < b
                    if ((parity ^ swapped) % 2) 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];
                    }
                    continue;
                }
                int parity = Partition.Sum (Lf + 1, Q);
//                cerr << id<<":"<<Lf + 1 <<" " <<values_Range.getMx(4, 4) <<" "<<parity <<" 123123\n";
                if (parity & 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];
        }
//        cerr << "\n";
        cout<<res <<"\n";
    }
}
void solution() {
    cin >> n >> Q;
//    n = Rand(1, 10);
//    Q = Rand(1, 10);
//    cout << n << " "<<Q<<"\n";
    rep (i, 1, n) {
        cin >> arr[i].a >> arr[i].b;
//        arr[i].a = Rand(1, 10);
//        arr[i].b = Rand(1, 10);
//        cout << arr[i].a <<" "<<arr[i].b <<"\n";
    }
    rep (i, 1, Q) {
        cin >> qr[i];
//        qr[i] = Rand(1, 10);
//        cout << qr[i] <<"\n";
    }
//    {
//        cout<<"\n";
//        int res = 0;
//        rep (i, 1, n) {
//            vector<int> cur = {arr[i].a, arr[i].b};
//            int pos = 0;
//            rep (j, 1, Q) {
//                if (cur[pos] <= qr[j]) pos ^= 1;
//            }
//            res += cur[pos];
//            cout << cur[pos] <<" ";
//        }
//        cout<<"\n";
//        cout << res <<"\n";
//    }
    sub3 :: solution();
}

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

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

5->9->5->9
_|_|_
babab
1 4
2 7
4
2
10
9

10 8
3 9
10 10
6 2
7 10
3 8
10 3
4 8
7 9
1 1
2 5
7
4
4
3
2
7
4
3



*/

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 function 'void sub3::solution()':
fortune_telling2.cpp:162:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  162 |                     int mid = Lf + Rt + 1 >> 1;
      |                               ~~~~~~~~^~~
fortune_telling2.cpp: In member function 'int sub3::Segment_Tree_helper1::get(int, int, int, int, int, int)':
fortune_telling2.cpp:87:9: warning: control reaches end of non-void function [-Wreturn-type]
   87 |         }
      |         ^

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 21432 KB Output is correct
3 Correct 6 ms 19548 KB Output is correct
4 Correct 6 ms 19548 KB Output is correct
5 Correct 6 ms 19548 KB Output is correct
6 Correct 6 ms 19548 KB Output is correct
7 Correct 6 ms 19520 KB Output is correct
8 Correct 6 ms 21596 KB Output is correct
9 Correct 6 ms 19548 KB Output is correct
10 Correct 6 ms 21340 KB Output is correct
11 Correct 6 ms 21340 KB Output is correct
12 Correct 6 ms 21560 KB Output is correct
13 Correct 6 ms 21340 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 21432 KB Output is correct
3 Correct 6 ms 19548 KB Output is correct
4 Correct 6 ms 19548 KB Output is correct
5 Correct 6 ms 19548 KB Output is correct
6 Correct 6 ms 19548 KB Output is correct
7 Correct 6 ms 19520 KB Output is correct
8 Correct 6 ms 21596 KB Output is correct
9 Correct 6 ms 19548 KB Output is correct
10 Correct 6 ms 21340 KB Output is correct
11 Correct 6 ms 21340 KB Output is correct
12 Correct 6 ms 21560 KB Output is correct
13 Correct 6 ms 21340 KB Output is correct
14 Correct 51 ms 25664 KB Output is correct
15 Correct 98 ms 28220 KB Output is correct
16 Correct 157 ms 30164 KB Output is correct
17 Correct 231 ms 32860 KB Output is correct
18 Correct 215 ms 32856 KB Output is correct
19 Correct 237 ms 32852 KB Output is correct
20 Correct 232 ms 32696 KB Output is correct
21 Correct 214 ms 32724 KB Output is correct
22 Correct 202 ms 32472 KB Output is correct
23 Correct 223 ms 29712 KB Output is correct
24 Correct 201 ms 30440 KB Output is correct
25 Correct 202 ms 32724 KB Output is correct
26 Correct 221 ms 31956 KB Output is correct
27 Correct 251 ms 32416 KB Output is correct
28 Correct 243 ms 32500 KB Output is correct
29 Correct 270 ms 31944 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 21432 KB Output is correct
3 Correct 6 ms 19548 KB Output is correct
4 Correct 6 ms 19548 KB Output is correct
5 Correct 6 ms 19548 KB Output is correct
6 Correct 6 ms 19548 KB Output is correct
7 Correct 6 ms 19520 KB Output is correct
8 Correct 6 ms 21596 KB Output is correct
9 Correct 6 ms 19548 KB Output is correct
10 Correct 6 ms 21340 KB Output is correct
11 Correct 6 ms 21340 KB Output is correct
12 Correct 6 ms 21560 KB Output is correct
13 Correct 6 ms 21340 KB Output is correct
14 Correct 51 ms 25664 KB Output is correct
15 Correct 98 ms 28220 KB Output is correct
16 Correct 157 ms 30164 KB Output is correct
17 Correct 231 ms 32860 KB Output is correct
18 Correct 215 ms 32856 KB Output is correct
19 Correct 237 ms 32852 KB Output is correct
20 Correct 232 ms 32696 KB Output is correct
21 Correct 214 ms 32724 KB Output is correct
22 Correct 202 ms 32472 KB Output is correct
23 Correct 223 ms 29712 KB Output is correct
24 Correct 201 ms 30440 KB Output is correct
25 Correct 202 ms 32724 KB Output is correct
26 Correct 221 ms 31956 KB Output is correct
27 Correct 251 ms 32416 KB Output is correct
28 Correct 243 ms 32500 KB Output is correct
29 Correct 270 ms 31944 KB Output is correct
30 Correct 419 ms 49464 KB Output is correct
31 Correct 666 ms 55152 KB Output is correct
32 Correct 926 ms 60992 KB Output is correct
33 Correct 1515 ms 81400 KB Output is correct
34 Correct 369 ms 50148 KB Output is correct
35 Correct 1514 ms 82956 KB Output is correct
36 Correct 1513 ms 82504 KB Output is correct
37 Correct 1499 ms 81880 KB Output is correct
38 Correct 1493 ms 81632 KB Output is correct
39 Correct 1510 ms 81344 KB Output is correct
40 Correct 1497 ms 81908 KB Output is correct
41 Correct 1480 ms 81596 KB Output is correct
42 Correct 1516 ms 81648 KB Output is correct
43 Correct 1439 ms 80280 KB Output is correct
44 Correct 1411 ms 80428 KB Output is correct
45 Correct 1420 ms 80560 KB Output is correct
46 Correct 1361 ms 62748 KB Output is correct
47 Correct 1411 ms 58320 KB Output is correct
48 Correct 1662 ms 73400 KB Output is correct
49 Correct 1560 ms 73456 KB Output is correct