Submission #952995

#	Time	Username	Problem	Language	Result	Execution time	Memory
952995		underwaterkillerwhale	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	1662 ms	82956 KiB

fortune_telling2

#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 (stderr)

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 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65