Submission #658160

#	Time	Username	Problem	Language	Result	Execution time	Memory
658160		Danilo21	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	4 / 100	105 ms	31856 KiB

fortune_telling2

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

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