#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = b; i >= a; i --)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPD(i, n) for (int i = n - 1; i >= 0; --i)
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void setupIO(){
#define name "Whisper"
//Phu Trong from Nguyen Tat Thanh High School for gifted student
srand(time(NULL));
cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
//freopen(name".inp", "r", stdin);
//freopen(name".out", "w", stdout);
cout << fixed << setprecision(10);
}
template <class X, class Y>
bool minimize(X &x, const Y &y){
X eps = 1e-9;
if (x > y + eps) {x = y; return 1;}
return 0;
}
template <class X, class Y>
bool maximize(X &x, const Y &y){
X eps = 1e-9;
if (x + eps < y) {x = y; return 1;}
return 0;
}
#define All(a...) a.begin(), a.end()
const int MAX = 2e5 + 5;
int nArr, numQuery;
pair<int, int> A[MAX];
int qs[MAX];
vector<int> comp;
int find(int x){
return lower_bound(All(comp), x) - comp.begin() + 1;
}
int st[MAX << 2], F[MAX];
void Modify(int nd, int l, int r, int pos, int val){
if (pos < l || pos > r) return;
if(l == r){
st[nd] = max(st[nd], val);
return;
}
int mid = (l + r) >> 1;
Modify(nd << 1, l, mid, pos, val);
Modify(nd << 1 | 1, mid + 1, r, pos, val);
st[nd] = max(st[nd << 1], st[nd << 1 | 1]);
}
int Query(int nd, int l, int r, int u, int v){
if (u > r || v < l) return 0;
if (u <= l && v >= r) return st[nd];
int mid = (l + r) >> 1;
int ql = Query(nd << 1, l, mid, u, v);
int qr = Query(nd << 1 | 1, mid + 1, r, u, v);
return max(ql, qr);
}
void Modify(int pos, int val){ Modify(1, 1, comp.size(), pos, val); }
int Query(int l, int r){ return Query(1, 1, comp.size(), l, r); }
void upd(int p, int val){
for (; p <= (int)comp.size(); p += p & (-p)) F[p] += val;
}
int get(int p){
int res = 0;
for (; p > 0; p -= p & (-p)) res += F[p];
return res;
}
vector<int> event[MAX];
void Whisper(){
cin >> nArr >> numQuery;
for (int i = 1; i <= nArr; ++i){
cin >> A[i].first >> A[i].second;
comp.push_back(A[i].first);
comp.push_back(A[i].second);
}
for (int i = 1; i <= numQuery; ++i){
cin >> qs[i];
comp.push_back(qs[i]);
}
sort(All(comp));
comp.resize(unique(All(comp)) - comp.begin());
for (int i = 1; i <= numQuery; ++i){
Modify(find(qs[i]), i);
}
int ans = 0;
for (int i = 1; i <= nArr; ++i){
int l = find(min(A[i].first, A[i].second));
int r = find(max(A[i].first, A[i].second));
if (l == r){
ans += A[i].first; continue;
}
int mx_id = Query(l, r - 1);
event[mx_id].emplace_back(i);
}
for (int i = numQuery; i >= 1; --i){
for (int &j : event[i]){
int v = find(max(A[j].first, A[j].second));
int turn = get((int)comp.size()) - get(v - 1);
if(turn & 1) {
ans += min(A[j].first, A[j].second);
}
else{
ans += max(A[j].first, A[j].second);
}
}
upd(find(qs[i]), 1);
}
for (int &j : event[0]){
int turn = get((int)comp.size());
if (turn & 1) ans += A[j].second;
else ans += A[j].first;
}
cout << ans;
/*
Case 1: if A(i).first <= qs(j) < A(i).second
-> the answer always = A(i).second
Case 2: if qs(j) > A(i).second
-> the cards is always turn down
Case 3: if qs(j) < A(i).first
-> The cards isn't affected
*/
}
signed main(){
setupIO();
int Test = 1;
// cin >> Test;
for ( int i = 1 ; i <= Test ; i++ ){
Whisper();
if (i < Test) cout << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
8796 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
5212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
