oj.uz

Submission #766273

# Submission time Handle Problem Language Result Execution time Memory
766273 2023-06-25T12:35:21 Z joelgun14 Fortune Telling 2 (JOI14_fortune_telling2) C++17
4 / 100
 313 ms 38116 KB 
// header file
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// pragma
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
// macros
#define endl "\n"
#define ll long long
#define mp make_pair
#define ins insert
#define lb lower_bound
#define pb push_back
#define ub upper_bound
#define lll __int128
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int lim = 1e9 + 5;
struct node {
    int l = -1, r = -1, val = -1;
};
struct segment_tree {
    vector<node> a = {node()};
    void update(int nd, int cl, int cr, int idx, int val) {
        //cout << "UPDATE " << nd << " " << cl << " " << cr << " " << idx << " " << val << endl;
        a[nd].val = max(a[nd].val, val);
        if(cl == cr) {
            return;
        }
        int mid = (cl + cr) / 2;
        if(idx <= mid) {
            if(a[nd].l == -1)
                a[nd].l = a.size(), a.pb(node());
            update(a[nd].l, cl, mid, idx, val);
        }
        else {
            if(a[nd].r == -1)
                a[nd].r = a.size(), a.pb(node());
            update(a[nd].r, mid + 1, cr, idx, val);
        }
    }
    int query(int nd, int cl, int cr, int l, int r) {
        //cout << "QUERY " << nd << " " << cl << " " << cr << " " << a[nd].l << " " << a[nd].r << " " << a[nd].val << endl;
        if(cl >= l && cr <= r) {
            return a[nd].val;
        }
        else if(cr < l || cl > r)
            return -1;
        else {
            int mid = (cl + cr) / 2;
            int ret = -1;
            if(a[nd].l != -1)
                ret = max(ret, query(a[nd].l, cl, mid, l, r));
            if(a[nd].r != -1)
                ret = max(ret, query(a[nd].r, mid + 1, cr, l, r));
            return ret;
        }
    }
};
struct fenwick {
    map<int, int> a;
    void update(int idx, int val) {
        ++idx;
        while(idx < lim) {
            a[idx] += val;
            idx += idx&-idx;
        }
    }
    int query(int idx) {
        ++idx;
        int ret = 0;
        while(idx) {
            ret += a[idx];
            idx -= idx&-idx;
        }
        return ret;
    }
    int query(int l, int r) {
        return query(r) - query(l - 1);
    }
};
int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    pair<int, int> a[n];
    for(int i = 0; i < n; ++i) {
        cin >> a[i].fi >> a[i].se;
    }
    // max only -> min
    // all -> only after last max only
    int b[k];
    segment_tree seg;
    for(int i = 0; i < k; ++i)
        cin >> b[i], seg.update(0, 0, lim - 1, b[i], i);
    ll res = 0;
    // isi -> kartu ke brp
    vector<int> v[k];
    vector<int> sisa;
    for(int i = 0; i < n; ++i) {
        // last occurence yg antara all dan mx
        int last_occur = seg.query(0, 0, lim - 1, min(a[i].fi, a[i].se), max(a[i].fi, a[i].se - 1));
        //cout << l << " " << r << " " << last_occur << endl;
        // consider cnt all mulai dari max
        // consider cnt all di kanan posisi skrg
        // di kanan last occur
        //cout << last_occur << " ";
        if(last_occur != -1) {
            v[last_occur].pb(i);
        }
        else {
            sisa.pb(i);
        }
    }
    //cout << endl;
    fenwick bit;    
    for(int i = k - 1; i >= 0; --i) {
        bit.update(b[i], 1);
        for(auto j : v[i]) {
            int cntall = bit.query(max(a[j].fi, a[j].se), 1e9);
            //cout << j << " " << cntall << endl;
            if(cntall & 1)
                res += min(a[j].fi, a[j].se);
            else
                res += max(a[j].fi, a[j].se);
            //cout << res << " ";
            //cout << res << endl;
        }
    }
    for(auto j : sisa) {
        int cntall = bit.query(max(a[j].fi, a[j].se), 1e9);
        if(cntall & 1)
            res += a[j].se;
        else
            res += a[j].fi;
        //cout << res << " ";
    }
    cout << res << endl;
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1104 KB Output is correct
2 Correct 4 ms 1288 KB Output is correct
3 Correct 5 ms 1592 KB Output is correct
4 Correct 5 ms 1488 KB Output is correct
5 Correct 5 ms 1508 KB Output is correct
6 Correct 5 ms 1488 KB Output is correct
7 Correct 5 ms 1488 KB Output is correct
8 Correct 5 ms 1488 KB Output is correct
9 Correct 4 ms 1104 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 6 ms 1488 KB Output is correct
12 Correct 5 ms 1488 KB Output is correct
13 Correct 5 ms 1556 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1104 KB Output is correct
2 Correct 4 ms 1288 KB Output is correct
3 Correct 5 ms 1592 KB Output is correct
4 Correct 5 ms 1488 KB Output is correct
5 Correct 5 ms 1508 KB Output is correct
6 Correct 5 ms 1488 KB Output is correct
7 Correct 5 ms 1488 KB Output is correct
8 Correct 5 ms 1488 KB Output is correct
9 Correct 4 ms 1104 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 6 ms 1488 KB Output is correct
12 Correct 5 ms 1488 KB Output is correct
13 Correct 5 ms 1556 KB Output is correct
14 Correct 56 ms 10992 KB Output is correct
15 Correct 116 ms 20340 KB Output is correct
16 Correct 196 ms 29228 KB Output is correct
17 Correct 313 ms 38040 KB Output is correct
18 Correct 268 ms 38028 KB Output is correct
19 Correct 269 ms 37812 KB Output is correct
20 Correct 283 ms 38116 KB Output is correct
21 Correct 257 ms 36764 KB Output is correct
22 Correct 112 ms 6632 KB Output is correct
23 Correct 107 ms 6004 KB Output is correct
24 Correct 82 ms 5448 KB Output is correct
25 Correct 147 ms 7544 KB Output is correct
26 Correct 203 ms 35348 KB Output is correct
27 Correct 230 ms 37740 KB Output is correct
28 Correct 222 ms 36444 KB Output is correct
29 Incorrect 305 ms 38068 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1104 KB Output is correct
2 Correct 4 ms 1288 KB Output is correct
3 Correct 5 ms 1592 KB Output is correct
4 Correct 5 ms 1488 KB Output is correct
5 Correct 5 ms 1508 KB Output is correct
6 Correct 5 ms 1488 KB Output is correct
7 Correct 5 ms 1488 KB Output is correct
8 Correct 5 ms 1488 KB Output is correct
9 Correct 4 ms 1104 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 6 ms 1488 KB Output is correct
12 Correct 5 ms 1488 KB Output is correct
13 Correct 5 ms 1556 KB Output is correct
14 Correct 56 ms 10992 KB Output is correct
15 Correct 116 ms 20340 KB Output is correct
16 Correct 196 ms 29228 KB Output is correct
17 Correct 313 ms 38040 KB Output is correct
18 Correct 268 ms 38028 KB Output is correct
19 Correct 269 ms 37812 KB Output is correct
20 Correct 283 ms 38116 KB Output is correct
21 Correct 257 ms 36764 KB Output is correct
22 Correct 112 ms 6632 KB Output is correct
23 Correct 107 ms 6004 KB Output is correct
24 Correct 82 ms 5448 KB Output is correct
25 Correct 147 ms 7544 KB Output is correct
26 Correct 203 ms 35348 KB Output is correct
27 Correct 230 ms 37740 KB Output is correct
28 Correct 222 ms 36444 KB Output is correct
29 Incorrect 305 ms 38068 KB Output isn't correct
30 Halted 0 ms 0 KB -