#include <bits/stdc++.h>
#define se second
#define fs first
#define pb push_back
#define ll long long
#define ii pair<ll,ll>
#define ld long double
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for (auto id : v)
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }
const int N = 2e5 + 7;
const int Mod = 1e9 + 7;
const int szBL = 500;
const int INF = 2e9 + 7;
const int BASE = 137;
struct Arr_Data {
int a, b;
bool isswapped;
Arr_Data () : a(0), b(0), isswapped(0) {};
};
///input:
int n, Q;
Arr_Data arr[N];
int qr[N];
///compress:
int num_Val;
vector<int> nen;
int CPR (int X) {
return lower_bound(ALL(nen), X) - nen.begin() + 1;
}
void compress () {
sort (ALL(nen));
nen.resize(num_Val = unique(ALL(nen)) - nen.begin());
rep (i, 1, n) {
arr[i].a = CPR(arr[i].a);
arr[i].b = CPR(arr[i].b);
}
rep (i, 1, Q) qr[i] = CPR(qr[i]);
}
///data:
vector<vector<int>> queries, events;
namespace sub3 {
struct Segment_Tree_helper1 {
int Range;
int st[3][N << 2];
void init(int n ) {
Range = n;
rep (i, 0, (Range + 1) << 2) st[0][i] = INF, st[1][i] = 0, st[0][i] = 0;
}
void update (int id, int l, int r, int pos, int val) {
if (l > pos || r < pos) return;
if (l == r) {
st[1][id] = st[0][id] = st[2][id] = val;
return;
}
int mid = l + r >> 1;
update (id << 1, l, mid, pos, val);
update (id << 1 | 1, mid + 1, r, pos, val);
st[0][id] = min(st[0][id << 1], st[0][id << 1 | 1]);
st[1][id] = max(st[1][id << 1], st[1][id << 1 | 1]);
st[2][id] = st[2][id << 1] + st[2][id << 1 | 1];
}
int get (int id, int l, int r, int u, int v, int typ) {
if (l > v || r < u) {
if (typ == 0) return INF;
else return 0;
}
if (l >= u && r <= v) return st[typ][id];
int mid = l + r >> 1;
if (typ == 1) return max(get (id << 1, l, mid, u, v, typ), get (id << 1 | 1, mid + 1, r, u, v, typ));
else if (typ == 0) return min(get (id << 1, l, mid, u, v, typ), get (id << 1 | 1, mid + 1, r, u, v, typ));
else if (typ == 2) return get (id << 1, l, mid, u, v, typ) + get (id << 1 | 1, mid + 1, r, u, v, typ);
}
int walk_Left (int id, int l, int r, int bound) { ///walk to Find L when the upper_bound is bound
if (l > bound) return -1;
if (st[1][id] == 0) return -1;
if (l == r) return l;
int mid = l + r >> 1;
int res = -1;
if (mid + 1 <= bound) res = walk_Left (id << 1 | 1 , mid + 1, r, bound);
if (res == -1) res = walk_Left (id << 1, l, mid, bound);
return res;
}
int walk_Right (int id, int l, int r, int bound) { ///walk to Find R when the lower_bound is bound
if (r < bound) return -1;
if (st[1][id] == 0) return -1;
if (l == r) return l;
int mid = l + r >> 1;
int res = -1;
if (mid >= bound) res = walk_Right (id << 1, l, mid, bound);
if (res == -1) res = walk_Right (id << 1 | 1, mid + 1, r, bound);
return res;
}
int search_smallest_pole (int id, int l, int r, int bound) { ///value need to strictly smaller the bound
if (st[0][id] >= bound) return -1;
if (l == r) return l;
int mid = l + r >> 1;
int res = -1;
if (st[0][id << 1 | 1] < bound) {
res = search_smallest_pole(id << 1, l, mid, bound);
if (res == -1) search_smallest_pole (id << 1 | 1, mid + 1, r, bound);
}
return res;
}
void update (int pos, int val) {
update (1, 0, Range, pos, val);
}
int getMx (int L, int R) {
return get (1, 0, Range, L, R, 1);
}
int getMn (int L, int R) {
return get (1, 0, Range, L, R, 0);
}
int Sum (int L, int R) {
return get (1, 0, Range, L, R, 2);
}
int walk_Left (int bound){
return walk_Left (1, 0, Range, bound);
}
int walk_Right (int bound) {
return walk_Right (1, 0, Range, bound);
}
int search_smallest_pole (int bound) {
return search_smallest_pole (1, 0, Range, bound);
}
}ST, Partition, values_Range;
void solution() {
nen = {0, INF};
rep (i, 1, n) nen.push_back(arr[i].a), nen.push_back(arr[i].b);
rep (i, 1, Q) nen.push_back(qr[i]);
compress();
events.resize(num_Val + 1, vector<int> (0));
queries.resize(num_Val + 1, vector<int> (0));
rep (i, 1, n) {
if (arr[i].a > arr[i].b) {
swap(arr[i].a, arr[i].b);
arr[i].isswapped = 1;
}
events[arr[i].b].push_back(i);
}
rep (i, 1, Q) queries[qr[i]].push_back(i);
ST.init(Q), Partition.init(Q), values_Range.init(Q);
rep (i, 1, Q) ST.update(i, qr[i]);
values_Range.update (0, ST.getMx(1, Q)); ///set stored maximum value of each range
vector<int> final_arr(n + 1, 0);
reb (X, num_Val, 1) {
iter (&id, queries[X]) {
int boundL = Partition.walk_Left(id - 1), boundR = Partition.walk_Right(id + 1);
if (boundL == -1) boundL = 0;
if (boundR == -1) boundR = Q + 1;
Partition.update (id, 1);
values_Range.update (id, ST.getMx(id + 1, boundR - 1)); ///dont need to consider the edgecase
values_Range.update (boundL, ST.getMx(boundL + 1, id - 1));
}
iter (&id, events[X]) {
int A = arr[id].a, B = arr[id].b, swapped = arr[id].isswapped;
int smallest_idx = values_Range.search_smallest_pole(arr[id].a);
if (smallest_idx == -1) smallest_idx = Q + 1;
// cout <<"183: "<<id<<": "<<smallest_idx<<" "<<"\n";
int parity = Partition.Sum(smallest_idx, Q) % 2;
if (swapped) {
if (smallest_idx == 0) parity ^= 1;
}
if (parity & 1) final_arr[id] = B;
else final_arr[id] = A;
}
}
ll res = 0;
rep (i, 1, n) {
// cout << nen[final_arr[i] - 1] << " ";
res += nen[final_arr[i] - 1];
}
cout << res <<"\n";
}
}
void solution() {
cin >> n >> Q;
rep (i, 1, n) {
cin >> arr[i].a >> arr[i].b;
}
rep (i, 1, Q) cin >> qr[i];
sub3 :: solution();
}
#define file(name) freopen(name".inp", "r", stdin);
//freopen(name".out", "w", stdout);
int main() {
// file("c");
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll num_Test = 1;
// cin >> num_Test;
while(num_Test--)
solution();
}
/*
4 4
aaab
1 4
1 3
3 4
2 4
*/
Compilation message
fortune_telling2.cpp: In member function 'void sub3::Segment_Tree_helper1::update(int, int, int, int, int)':
fortune_telling2.cpp:73:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
73 | int mid = l + r >> 1;
| ~~^~~
fortune_telling2.cpp: In member function 'int sub3::Segment_Tree_helper1::get(int, int, int, int, int, int)':
fortune_telling2.cpp:86:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
86 | int mid = l + r >> 1;
| ~~^~~
fortune_telling2.cpp: In member function 'int sub3::Segment_Tree_helper1::walk_Left(int, int, int, int)':
fortune_telling2.cpp:95:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
95 | int mid = l + r >> 1;
| ~~^~~
fortune_telling2.cpp: In member function 'int sub3::Segment_Tree_helper1::walk_Right(int, int, int, int)':
fortune_telling2.cpp:105:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
105 | int mid = l + r >> 1;
| ~~^~~
fortune_telling2.cpp: In member function 'int sub3::Segment_Tree_helper1::search_smallest_pole(int, int, int, int)':
fortune_telling2.cpp:115:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
115 | int mid = l + r >> 1;
| ~~^~~
fortune_telling2.cpp: In member function 'int sub3::Segment_Tree_helper1::get(int, int, int, int, int, int)':
fortune_telling2.cpp:90:9: warning: control reaches end of non-void function [-Wreturn-type]
90 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
21336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
21336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
21336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
