oj.uz

Submission #952994

# Submission time Handle Problem Language Result Execution time Memory
952994 2024-03-25T09:36:51 Z underwaterkillerwhale Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 3000 ms 71392 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 15 ms 21340 KB Output is correct
2 Correct 19 ms 21540 KB Output is correct
3 Correct 25 ms 19548 KB Output is correct
4 Correct 25 ms 19608 KB Output is correct
5 Correct 24 ms 19800 KB Output is correct
6 Correct 24 ms 19544 KB Output is correct
7 Correct 24 ms 19616 KB Output is correct
8 Correct 25 ms 21596 KB Output is correct
9 Correct 18 ms 19548 KB Output is correct
10 Correct 25 ms 21340 KB Output is correct
11 Correct 25 ms 21596 KB Output is correct
12 Correct 25 ms 21616 KB Output is correct
13 Correct 25 ms 21596 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 21340 KB Output is correct
2 Correct 19 ms 21540 KB Output is correct
3 Correct 25 ms 19548 KB Output is correct
4 Correct 25 ms 19608 KB Output is correct
5 Correct 24 ms 19800 KB Output is correct
6 Correct 24 ms 19544 KB Output is correct
7 Correct 24 ms 19616 KB Output is correct
8 Correct 25 ms 21596 KB Output is correct
9 Correct 18 ms 19548 KB Output is correct
10 Correct 25 ms 21340 KB Output is correct
11 Correct 25 ms 21596 KB Output is correct
12 Correct 25 ms 21616 KB Output is correct
13 Correct 25 ms 21596 KB Output is correct
14 Correct 237 ms 26452 KB Output is correct
15 Correct 495 ms 29852 KB Output is correct
16 Correct 731 ms 32976 KB Output is correct
17 Correct 988 ms 36260 KB Output is correct
18 Correct 1000 ms 36256 KB Output is correct
19 Correct 995 ms 36316 KB Output is correct
20 Correct 1123 ms 36388 KB Output is correct
21 Correct 989 ms 36244 KB Output is correct
22 Correct 972 ms 35012 KB Output is correct
23 Correct 983 ms 32976 KB Output is correct
24 Correct 966 ms 33452 KB Output is correct
25 Correct 986 ms 35660 KB Output is correct
26 Correct 925 ms 34996 KB Output is correct
27 Correct 1041 ms 36292 KB Output is correct
28 Correct 1024 ms 36100 KB Output is correct
29 Correct 852 ms 35116 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 21340 KB Output is correct
2 Correct 19 ms 21540 KB Output is correct
3 Correct 25 ms 19548 KB Output is correct
4 Correct 25 ms 19608 KB Output is correct
5 Correct 24 ms 19800 KB Output is correct
6 Correct 24 ms 19544 KB Output is correct
7 Correct 24 ms 19616 KB Output is correct
8 Correct 25 ms 21596 KB Output is correct
9 Correct 18 ms 19548 KB Output is correct
10 Correct 25 ms 21340 KB Output is correct
11 Correct 25 ms 21596 KB Output is correct
12 Correct 25 ms 21616 KB Output is correct
13 Correct 25 ms 21596 KB Output is correct
14 Correct 237 ms 26452 KB Output is correct
15 Correct 495 ms 29852 KB Output is correct
16 Correct 731 ms 32976 KB Output is correct
17 Correct 988 ms 36260 KB Output is correct
18 Correct 1000 ms 36256 KB Output is correct
19 Correct 995 ms 36316 KB Output is correct
20 Correct 1123 ms 36388 KB Output is correct
21 Correct 989 ms 36244 KB Output is correct
22 Correct 972 ms 35012 KB Output is correct
23 Correct 983 ms 32976 KB Output is correct
24 Correct 966 ms 33452 KB Output is correct
25 Correct 986 ms 35660 KB Output is correct
26 Correct 925 ms 34996 KB Output is correct
27 Correct 1041 ms 36292 KB Output is correct
28 Correct 1024 ms 36100 KB Output is correct
29 Correct 852 ms 35116 KB Output is correct
30 Correct 2252 ms 57036 KB Output is correct
31 Correct 2868 ms 64908 KB Output is correct
32 Execution timed out 3046 ms 71392 KB Time limit exceeded
33 Halted 0 ms 0 KB -