oj.uz

Submission #658181

# Submission time Handle Problem Language Result Execution time Memory
658181 2022-11-12T10:50:05 Z Danilo21 Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 896 ms 181752 KB 
#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define en '\n'
#define sp ' '
#define tb '\t'
#define ri(n) int n; cin >> n
#define rl(n) ll n; cin >> n
#define rs(s) string s; cin >> s
#define rc(c) char c; cin >> c
#define rv(v) for (auto &x : v) cin >> x
#define pven(v) for (auto x : v) cout << x << en
#define pv(v) for (auto x : v) cout << x << sp; cout << en
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yes cout << "YES" << en
#define no cout << "NO" << en
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define ssort(a, b) if (a < b) swap(a, b)
#define bitcnt(a) (__builtin_popcountll(a))
#define bithigh(a) (63-__builtin_clzll(a))
#define lg bithigh
#define highpow(a) (1LL << (ll)lg(a))

using namespace std;

template<class T>
class node{
public:
    T val;
    node<T>* ch[2];
    node<T>(){}
    node<T>(T val = T()){
        this->val = val;
        this->ch[0] = this->ch[1] = nullptr;
    }
    ~node<T>(){ delete this->ch[0]; delete this->ch[1]; }
    void add(int x, T val = T()){ this->ch[x] = new node<T>(val); }
};
template<class T>
class implicit_segtree{
private:
    ll left, right;
    node<T>* root;
    void init(ll l, ll r){
        ll n = r-l+1;
        if (highpow(n)^n) n = 2*highpow(n);
        this->left = l;
        this->right = l+n-1;
        root = new node<T>(T());
    }
    node<T>* ch(node<T>* s, int x){
        if (!s->ch[x]) s->add(x);
        return s->ch[x];
    }
    T update(node<T>* s, ll l, ll r, ll pos, T x){
        if (l > pos || r < pos) return s->val;
        if (l == r) return s->val.up(T(x));

        T a = T(), b = T();
        ll m = floor((double)(l + r) / 2.0);
        if (pos <= m){
            a = update(ch(s, 0), l, m, pos, x);
            if (s->ch[1]) b = ch(s, 1)->val;
        }
        else{
            b = update(ch(s, 1), m+1, r, pos, x);
            if (s->ch[0]) a = ch(s, 0)->val;
        }
        return s->val = T::op(a, b);
    }
    T query(node<T>* s, ll l, ll r, ll ql, ll qr){
        if (l > qr || r < ql) return T::null_v();
        if (l >= ql && r <= qr) return s->val;

        T a = T(), b = T();
        ll m = floor((double)(l + r) / 2.0);
        if (ql > m) a = T::null_v();
        if (qr <= m) b = T::null_v();

        if (s->ch[0]) a = query(ch(s, 0), l, m, ql, qr);
        if (s->ch[1]) b = query(ch(s, 1), m+1, r, ql, qr);
        return T::op(a, b);
    }
public:
    implicit_segtree(){}
    implicit_segtree(ll l, ll r){ init(l, r); }
    ~implicit_segtree(){ delete this->root; }
    void update(ll pos, auto x){ update(this->root, this->left, this->right, pos, T(x)); }
    auto query(ll l, ll r){ if (l > r) return T::null_v().val; return query(this->root, this->left, this->right, l, r).val; }
};
class sum_t{
public:
    ll val;

    sum_t(ll val = 0){ this->val = val; }
    static sum_t null_v(){ return sum_t(0); }

    static sum_t op(const sum_t& a, const sum_t& b){ return a + b; }
    // This is currently on set mode but it can be on add.
    sum_t up(const sum_t& a){ return *this += a; }
    void lazy_op(const sum_t& a, int l){ up(sum_t(a.val * l)); }

    sum_t operator =(const sum_t& a){ this->val = a.val; return *this; }
    sum_t operator +=(const sum_t& a) { this->val += a.val; return *this; }
    sum_t operator -=(const sum_t& a) { this->val -= a.val; return *this; }
    sum_t operator +(const sum_t& a) const { return sum_t(this->val + a.val); }
    sum_t operator -(const sum_t& a) const { return sum_t(this->val - a.val); }
    bool operator ==(const sum_t& a) const { return this->val == a.val; }
    bool operator !=(const sum_t& a) const { return this->val != a.val; }

    void Print() const { cout << this->val << sp; }
    void log() const { cerr << this->val << sp; }
};
const ll LINF = 4e18;
class max_t{
public:
    ll val;

    max_t(ll val = -1){ this->val = val; }
    static max_t null_v(){ return max_t(-1); }

    static max_t op(const max_t& a, const max_t& b){ return max_t(max(a.val, b.val)); }
    // This is currently on set mode but it can be on add.
    max_t up(const max_t& a){ return *this = a; }
    void lazy_op(const max_t& a, int l){ up(a); }

    max_t operator =(const max_t& a){ this->val = a.val; return *this; }
    max_t operator +=(const max_t& a) { this->val += a.val; return *this; }
    max_t operator -=(const max_t& a) { this->val -= a.val; return *this; }
    max_t operator +(const max_t& a) const { return max_t(this->val + a.val); }
    max_t operator -(const max_t& a) const { return max_t(this->val - a.val); }
    bool operator ==(const max_t& a) const { return this->val == a.val; }
    bool operator !=(const max_t& a) const { return this->val != a.val; }

    void Print() const { cout << this->val << sp; }
    void log() const { cerr << this->val << sp; }
};

const int mxN = 1e6+10, INF = 2e9;
ll n, m, a[mxN], b[mxN], c[mxN], ans[mxN];
array<ll, 2> d[mxN];
implicit_segtree<max_t>* st1;
implicit_segtree<sum_t>* st2;

void Solve(){

    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> a[i] >> b[i];
    st1 = new implicit_segtree<max_t>(0, INF);
    for (int i = 0; i < m; i++){
        cin >> c[i];
        st1->update(c[i], i);
    }
    for (int i = 0; i < n; i++)
        d[i] = {st1->query(min(a[i], b[i]), max(a[i], b[i])-1), i};
    sort(d, d+n); reverse(d, d+n);
    st2 = new implicit_segtree<sum_t>(0, INF);
    ll sum = 0;
    for (int i = 0, j = m-1; i < n; i++){
        while (j > d[i][0]){
            st2->update(c[j], 1);
            j--;
        }
        int t = d[i][1];
        ll ans = st2->query(max(a[t], b[t]), INF);
        if (~d[i][0]) ssort(a[t], b[t]);
        sum += (ans&1 ? b[t] : a[t]);
    }
    cout << sum << en;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0); cerr.tie(0);
    cout << setprecision(12) << fixed;
    cerr << setprecision(12) << fixed;
    cerr << "Started!" << endl;

    int t = 1;
    //cin >> t;
    while (t--)
        Solve();

    return 0;
}

Compilation message

fortune_telling2.cpp:94:25: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   94 |     void update(ll pos, auto x){ update(this->root, this->left, this->right, pos, T(x)); }
      |                         ^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1236 KB Output is correct
2 Correct 4 ms 1620 KB Output is correct
3 Correct 4 ms 1492 KB Output is correct
4 Correct 5 ms 1748 KB Output is correct
5 Correct 3 ms 1620 KB Output is correct
6 Correct 4 ms 1088 KB Output is correct
7 Correct 4 ms 1624 KB Output is correct
8 Correct 2 ms 980 KB Output is correct
9 Correct 2 ms 980 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 4 ms 1620 KB Output is correct
12 Correct 4 ms 1664 KB Output is correct
13 Correct 4 ms 1624 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1236 KB Output is correct
2 Correct 4 ms 1620 KB Output is correct
3 Correct 4 ms 1492 KB Output is correct
4 Correct 5 ms 1748 KB Output is correct
5 Correct 3 ms 1620 KB Output is correct
6 Correct 4 ms 1088 KB Output is correct
7 Correct 4 ms 1624 KB Output is correct
8 Correct 2 ms 980 KB Output is correct
9 Correct 2 ms 980 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 4 ms 1620 KB Output is correct
12 Correct 4 ms 1664 KB Output is correct
13 Correct 4 ms 1624 KB Output is correct
14 Correct 34 ms 12076 KB Output is correct
15 Correct 64 ms 20152 KB Output is correct
16 Correct 101 ms 32564 KB Output is correct
17 Correct 131 ms 39580 KB Output is correct
18 Correct 148 ms 42452 KB Output is correct
19 Correct 109 ms 22804 KB Output is correct
20 Correct 134 ms 42320 KB Output is correct
21 Correct 111 ms 22604 KB Output is correct
22 Correct 65 ms 5512 KB Output is correct
23 Correct 73 ms 5096 KB Output is correct
24 Correct 78 ms 4684 KB Output is correct
25 Correct 68 ms 6092 KB Output is correct
26 Correct 159 ms 41652 KB Output is correct
27 Correct 141 ms 42320 KB Output is correct
28 Correct 121 ms 36664 KB Output is correct
29 Correct 156 ms 42440 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1236 KB Output is correct
2 Correct 4 ms 1620 KB Output is correct
3 Correct 4 ms 1492 KB Output is correct
4 Correct 5 ms 1748 KB Output is correct
5 Correct 3 ms 1620 KB Output is correct
6 Correct 4 ms 1088 KB Output is correct
7 Correct 4 ms 1624 KB Output is correct
8 Correct 2 ms 980 KB Output is correct
9 Correct 2 ms 980 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 4 ms 1620 KB Output is correct
12 Correct 4 ms 1664 KB Output is correct
13 Correct 4 ms 1624 KB Output is correct
14 Correct 34 ms 12076 KB Output is correct
15 Correct 64 ms 20152 KB Output is correct
16 Correct 101 ms 32564 KB Output is correct
17 Correct 131 ms 39580 KB Output is correct
18 Correct 148 ms 42452 KB Output is correct
19 Correct 109 ms 22804 KB Output is correct
20 Correct 134 ms 42320 KB Output is correct
21 Correct 111 ms 22604 KB Output is correct
22 Correct 65 ms 5512 KB Output is correct
23 Correct 73 ms 5096 KB Output is correct
24 Correct 78 ms 4684 KB Output is correct
25 Correct 68 ms 6092 KB Output is correct
26 Correct 159 ms 41652 KB Output is correct
27 Correct 141 ms 42320 KB Output is correct
28 Correct 121 ms 36664 KB Output is correct
29 Correct 156 ms 42440 KB Output is correct
30 Correct 323 ms 93764 KB Output is correct
31 Correct 593 ms 174088 KB Output is correct
32 Correct 707 ms 176392 KB Output is correct
33 Correct 821 ms 176396 KB Output is correct
34 Correct 270 ms 87676 KB Output is correct
35 Correct 839 ms 181664 KB Output is correct
36 Correct 836 ms 181752 KB Output is correct
37 Correct 896 ms 181632 KB Output is correct
38 Correct 605 ms 97856 KB Output is correct
39 Correct 811 ms 181692 KB Output is correct
40 Correct 513 ms 97664 KB Output is correct
41 Correct 573 ms 97936 KB Output is correct
42 Correct 601 ms 97996 KB Output is correct
43 Correct 458 ms 95076 KB Output is correct
44 Correct 406 ms 90856 KB Output is correct
45 Correct 401 ms 82612 KB Output is correct
46 Correct 423 ms 24632 KB Output is correct
47 Correct 335 ms 24260 KB Output is correct
48 Correct 685 ms 179840 KB Output is correct
49 Correct 697 ms 174540 KB Output is correct