#include <bits/stdc++.h>
using namespace std;
void main_program();
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
main_program();
}
// #define int long long
struct MaxImplicitSegtree{
int lb, rb;
MaxImplicitSegtree *leftnode, *rightnode;
int mx;
MaxImplicitSegtree(int L, int R): lb(L), rb(R), leftnode(nullptr), rightnode(nullptr), mx(-1) {}
void extend(){
if (lb == rb) return;
if (leftnode) return;
int mid = (lb + rb) >> 1;
leftnode = new MaxImplicitSegtree(lb, mid);
rightnode = new MaxImplicitSegtree(mid+1, rb);
}
int get(int l, int r){
if (l <= lb && rb <= r) return mx;
if (lb > r || rb < l) return -1;
extend();
return max(leftnode->get(l, r), rightnode->get(l, r));
}
void update(int x, int val){
if (lb == x && rb == x) mx = val;
else{
extend();
int mid = (lb + rb) >> 1;
if (x <= mid) leftnode->update(x, val);
else rightnode->update(x, val);
mx = max(leftnode->mx, rightnode->mx);
}
}
};
struct SumImplicitSegtree{
int lb, rb;
SumImplicitSegtree *leftnode, *rightnode;
int sum;
SumImplicitSegtree(int L, int R): lb(L), rb(R), leftnode(nullptr), rightnode(nullptr), sum(0) {}
void extend(){
if (lb == rb) return;
if (leftnode) return;
int mid = (lb + rb) >> 1;
leftnode = new SumImplicitSegtree(lb, mid);
rightnode = new SumImplicitSegtree(mid+1, rb);
}
int get(int l, int r){
if (l <= lb && rb <= r) return sum;
if (lb > r || rb < l) return 0;
extend();
return leftnode->get(l, r) + rightnode->get(l, r);
}
void update(int x, int delta){
if (lb == x && rb == x) sum += delta;
else{
extend();
int mid = (lb + rb) >> 1;
if (x <= mid) leftnode->update(x, delta);
else rightnode->update(x, delta);
sum = leftnode->sum + rightnode->sum;
}
}
};
const int inf = 1e9 + 1;
int n, q;
vector<pair<int, int>> cards;
vector<int> MN, MX, qs, lst, inv;
void main_program(){
cin >> n >> q;
qs.resize(q);
cards.resize(n);
MN.resize(n);
MX.resize(n);
lst.assign(n, -1);
inv.assign(n, 0);
for (int i = 0; i < n; i++){
int A, B; cin >> A >> B;
cards[i] = {A, B};
MN[i] = min(A, B); MX[i] = max(A, B);
}
for (int i = 0; i < q; i++){
cin >> qs[i];
}
map<int, int> compress;
for (auto i: cards){
compress[i.first] = compress[i.second] = 1;
}
for (auto i: qs) compress[i] = 1;
int cp = 1;
for (auto &[key, value]: compress) value = cp++;
for (auto &i: cards) i = {compress[i.first], compress[i.second]};
for (auto &i: MN) i = compress[i];
for (auto &i: MX) i = compress[i];
for (auto &i: qs) i = compress[i];
MaxImplicitSegtree ist(1, cp);
for (int i = 0; i < q; i++){
ist.update(qs[i], i);
}
for (int i = 0; i < n; i++){
if (MX[i] > MN[i]) lst[i] = ist.get(MN[i], MX[i] - 1);
}
// for (int i = 0; i < n; i++) cout << lst[i] << " ";
// cout << "\n";
SumImplicitSegtree sst(1, cp);
vector<vector<int>> radix(q + 1);
for (int i = 0; i < n; i++) radix[lst[i] + 1].push_back(i);
for (int i = q-1; i >= 0; i--){
sst.update(qs[i], 1);
for (auto j: radix[i]){
// cout << j << "\n";
inv[j] = sst.get(MX[j], cp);
}
}
// for (int i = 0; i < n; i++) cout << inv[i] << " ";
// cout << "\n";
long long res = 0;
for (int i = 0; i < n; i++){
int crr;
if (lst[i] >= 0) crr = MX[i];
else crr = cards[i].first;
if (inv[i] & 1) crr = cards[i].first + cards[i].second - crr;
// cout << crr << "\n";
res += crr;
}
cout << res << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
