Submission #658160

# Submission time Handle Problem Language Result Execution time Memory
658160 2022-11-12T10:06:27 Z Danilo21 Fortune Telling 2 (JOI14_fortune_telling2) C++17
4 / 100
105 ms 31856 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 = 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)); }
      |                         ^~~~
# Verdict Execution time Memory Grader output
1 Correct 4 ms 1236 KB Output is correct
2 Correct 3 ms 1620 KB Output is correct
3 Correct 4 ms 1492 KB Output is correct
4 Correct 3 ms 1620 KB Output is correct
5 Correct 4 ms 1492 KB Output is correct
6 Correct 2 ms 980 KB Output is correct
7 Correct 4 ms 1620 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 340 KB Output is correct
11 Correct 3 ms 1620 KB Output is correct
12 Correct 3 ms 1620 KB Output is correct
13 Correct 4 ms 1620 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 1236 KB Output is correct
2 Correct 3 ms 1620 KB Output is correct
3 Correct 4 ms 1492 KB Output is correct
4 Correct 3 ms 1620 KB Output is correct
5 Correct 4 ms 1492 KB Output is correct
6 Correct 2 ms 980 KB Output is correct
7 Correct 4 ms 1620 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 340 KB Output is correct
11 Correct 3 ms 1620 KB Output is correct
12 Correct 3 ms 1620 KB Output is correct
13 Correct 4 ms 1620 KB Output is correct
14 Correct 30 ms 11708 KB Output is correct
15 Correct 65 ms 19580 KB Output is correct
16 Incorrect 105 ms 31856 KB Output isn't correct
17 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 4 ms 1236 KB Output is correct
2 Correct 3 ms 1620 KB Output is correct
3 Correct 4 ms 1492 KB Output is correct
4 Correct 3 ms 1620 KB Output is correct
5 Correct 4 ms 1492 KB Output is correct
6 Correct 2 ms 980 KB Output is correct
7 Correct 4 ms 1620 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 340 KB Output is correct
11 Correct 3 ms 1620 KB Output is correct
12 Correct 3 ms 1620 KB Output is correct
13 Correct 4 ms 1620 KB Output is correct
14 Correct 30 ms 11708 KB Output is correct
15 Correct 65 ms 19580 KB Output is correct
16 Incorrect 105 ms 31856 KB Output isn't correct
17 Halted 0 ms 0 KB -