Submission #652794

#TimeUsernameProblemLanguageResultExecution timeMemory
652794Danilo21Fortune Telling 2 (JOI14_fortune_telling2)C++17
0 / 100
3 ms1236 KiB
#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 = 0){ this->val = val; } static max_t null_v(){ return max_t(-LINF); } 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>>1); 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])), i}; sort(d, d+n); reverse(d, d+n); st2 = new implicit_segtree<sum_t>(0, INF>>1); ll sum = 0; for (int i = n-1, j = m-1; ~i; i--){ while (j > d[i][0]+1){ 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] != -LINF) 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)); }
      |                         ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...