oj.uz

Submission #766275

# Submission time Handle Problem Language Result Execution time Memory
766275 2023-06-25T12:36:38 Z joelgun14 Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 2684 ms 162128 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 1360 KB Output is correct
3 Correct 5 ms 1608 KB Output is correct
4 Correct 6 ms 1488 KB Output is correct
5 Correct 6 ms 1488 KB Output is correct
6 Correct 5 ms 1476 KB Output is correct
7 Correct 5 ms 1488 KB Output is correct
8 Correct 5 ms 1480 KB Output is correct
9 Correct 4 ms 1100 KB Output is correct
10 Correct 2 ms 324 KB Output is correct
11 Correct 5 ms 1480 KB Output is correct
12 Correct 5 ms 1488 KB Output is correct
13 Correct 5 ms 1488 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1104 KB Output is correct
2 Correct 4 ms 1360 KB Output is correct
3 Correct 5 ms 1608 KB Output is correct
4 Correct 6 ms 1488 KB Output is correct
5 Correct 6 ms 1488 KB Output is correct
6 Correct 5 ms 1476 KB Output is correct
7 Correct 5 ms 1488 KB Output is correct
8 Correct 5 ms 1480 KB Output is correct
9 Correct 4 ms 1100 KB Output is correct
10 Correct 2 ms 324 KB Output is correct
11 Correct 5 ms 1480 KB Output is correct
12 Correct 5 ms 1488 KB Output is correct
13 Correct 5 ms 1488 KB Output is correct
14 Correct 53 ms 10864 KB Output is correct
15 Correct 133 ms 20496 KB Output is correct
16 Correct 240 ms 29284 KB Output is correct
17 Correct 286 ms 37932 KB Output is correct
18 Correct 284 ms 38008 KB Output is correct
19 Correct 280 ms 37788 KB Output is correct
20 Correct 266 ms 38096 KB Output is correct
21 Correct 248 ms 36680 KB Output is correct
22 Correct 115 ms 6588 KB Output is correct
23 Correct 107 ms 6028 KB Output is correct
24 Correct 98 ms 5408 KB Output is correct
25 Correct 143 ms 7588 KB Output is correct
26 Correct 218 ms 35148 KB Output is correct
27 Correct 233 ms 37752 KB Output is correct
28 Correct 233 ms 36380 KB Output is correct
29 Correct 309 ms 38084 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1104 KB Output is correct
2 Correct 4 ms 1360 KB Output is correct
3 Correct 5 ms 1608 KB Output is correct
4 Correct 6 ms 1488 KB Output is correct
5 Correct 6 ms 1488 KB Output is correct
6 Correct 5 ms 1476 KB Output is correct
7 Correct 5 ms 1488 KB Output is correct
8 Correct 5 ms 1480 KB Output is correct
9 Correct 4 ms 1100 KB Output is correct
10 Correct 2 ms 324 KB Output is correct
11 Correct 5 ms 1480 KB Output is correct
12 Correct 5 ms 1488 KB Output is correct
13 Correct 5 ms 1488 KB Output is correct
14 Correct 53 ms 10864 KB Output is correct
15 Correct 133 ms 20496 KB Output is correct
16 Correct 240 ms 29284 KB Output is correct
17 Correct 286 ms 37932 KB Output is correct
18 Correct 284 ms 38008 KB Output is correct
19 Correct 280 ms 37788 KB Output is correct
20 Correct 266 ms 38096 KB Output is correct
21 Correct 248 ms 36680 KB Output is correct
22 Correct 115 ms 6588 KB Output is correct
23 Correct 107 ms 6028 KB Output is correct
24 Correct 98 ms 5408 KB Output is correct
25 Correct 143 ms 7588 KB Output is correct
26 Correct 218 ms 35148 KB Output is correct
27 Correct 233 ms 37752 KB Output is correct
28 Correct 233 ms 36380 KB Output is correct
29 Correct 309 ms 38084 KB Output is correct
30 Correct 977 ms 105400 KB Output is correct
31 Correct 1272 ms 117576 KB Output is correct
32 Correct 1609 ms 132676 KB Output is correct
33 Correct 2264 ms 161348 KB Output is correct
34 Correct 963 ms 102172 KB Output is correct
35 Correct 2466 ms 161384 KB Output is correct
36 Correct 2684 ms 161512 KB Output is correct
37 Correct 2289 ms 161408 KB Output is correct
38 Correct 2216 ms 160908 KB Output is correct
39 Correct 2158 ms 162128 KB Output is correct
40 Correct 1989 ms 151556 KB Output is correct
41 Correct 2044 ms 161788 KB Output is correct
42 Correct 2005 ms 162028 KB Output is correct
43 Correct 1453 ms 114872 KB Output is correct
44 Correct 1356 ms 110076 KB Output is correct
45 Correct 1398 ms 100640 KB Output is correct
46 Correct 731 ms 29404 KB Output is correct
47 Correct 582 ms 25244 KB Output is correct
48 Correct 1626 ms 158808 KB Output is correct
49 Correct 1717 ms 153624 KB Output is correct