#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>>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])-1), i};
sort(d, d+n); reverse(d, d+n);
st2 = new implicit_segtree<sum_t>(0, INF>>1);
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 |
2 ms |
1236 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1680 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1492 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1624 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1540 KB |
Output is correct |
| 6 |
Correct |
3 ms |
988 KB |
Output is correct |
| 7 |
Correct |
4 ms |
1620 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1108 KB |
Output is correct |
| 9 |
Correct |
2 ms |
984 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 |
1620 KB |
Output is correct |
| 13 |
Correct |
4 ms |
1748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1680 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1492 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1624 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1540 KB |
Output is correct |
| 6 |
Correct |
3 ms |
988 KB |
Output is correct |
| 7 |
Correct |
4 ms |
1620 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1108 KB |
Output is correct |
| 9 |
Correct |
2 ms |
984 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 |
1620 KB |
Output is correct |
| 13 |
Correct |
4 ms |
1748 KB |
Output is correct |
| 14 |
Correct |
35 ms |
12104 KB |
Output is correct |
| 15 |
Correct |
64 ms |
20156 KB |
Output is correct |
| 16 |
Incorrect |
117 ms |
32672 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1236 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1680 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1492 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1624 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1540 KB |
Output is correct |
| 6 |
Correct |
3 ms |
988 KB |
Output is correct |
| 7 |
Correct |
4 ms |
1620 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1108 KB |
Output is correct |
| 9 |
Correct |
2 ms |
984 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 |
1620 KB |
Output is correct |
| 13 |
Correct |
4 ms |
1748 KB |
Output is correct |
| 14 |
Correct |
35 ms |
12104 KB |
Output is correct |
| 15 |
Correct |
64 ms |
20156 KB |
Output is correct |
| 16 |
Incorrect |
117 ms |
32672 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
