#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j); i >= (k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
#define pb push_back
const int INF = (int)1e9;
typedef long long ll;
struct segmax{
vector<int> tree;
int n;
segmax(int sz, vector<int> &init){
n = 1;
while(n < sz) n *= 2;
tree.resize(2 * n, -INF);
REP(i, n){
if(i < init.size()){
tree[i + n] = init[i];
}
}
FOR(i, n - 1, 1, 1){
tree[i] = max(tree[i << 1], tree[i << 1 | 1]);
}
}
int query(int l, int r, int beg, int end, int v){
if(beg >= l && end <= r){
return tree[v];
}
if(beg >= r || end <= l)
return -INF;
int mid = (beg + end) >> 1;
return max(query(l, r, beg, mid, v << 1), query(l, r, mid, end, v << 1 | 1));
}
};
// for offline get number of elements > x in segment [l, r];
struct segsum{
vector<int> tree;
int n;
segsum(int sz){
n = 1;
while(n < sz) n *= 2;
tree.resize(2 * n, 0);
}
int query(int l, int r, int beg, int end, int v){
if(beg >= l && end <= r){
return tree[v];
}
if(beg >= r || end <= l)
return 0;
int mid = (beg + end) >> 1;
return query(l, r, beg, mid, v << 1) + query(l, r, mid, end, v << 1 | 1);
}
void upd(int pos, int val){
pos += n;
tree[pos] += val;
for(int i = pos / 2; i > 0; i /= 2){
tree[i] = tree[i << 1] + tree[i << 1 | 1];
}
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
const int mx = 700000;
int n, k;
cin >> n >> k;
vector<int> a(n), b(n);
vector<int> comp;
REP(i, n){
cin >> a[i] >> b[i];
comp.pb(a[i]);
comp.pb(b[i]);
}
vector<int> t(k);
REP(i, k){
cin >> t[i];
comp.pb(t[i]);
}
vector<int> oa = a, ob = b, ot = t; // to get sum later
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
REP(i, n){
a[i] = lower_bound(comp.begin(), comp.end(), a[i]) - comp.begin();
b[i] = lower_bound(comp.begin(), comp.end(), b[i]) - comp.begin();
}
REP(i, k){
t[i] = lower_bound(comp.begin(), comp.end(), t[i]) - comp.begin();
}
vector<int> numflips(n, 0);
vector<int> determined_side(n, 0); // which side is it after finding the last one that determines;that is biggest j,so that T[j] >= a && t[j] < b
vector<int> initmax(mx, -INF);
REP(i, k){
initmax[t[i]] = max(initmax[t[i]], i);
}
struct query{
int x, tl, query_index, sign;
bool operator<(query &oth){
return tie(x, tl, query_index, sign) < tie(oth.x, oth.tl, oth.query_index, sign);
}
};
vector<query> queries;
segmax st(mx, initmax);
REP(i, n){
int f = a[i], s = b[i];
if(f > s) swap(f, s);
int l = -INF, r = mx; // get number of j, to that t[j] >= max(a[i], b[i]) and index > x; go in order of j, add to segsum at t[j];
// [l, r) are based on indices
if(f != s){
l = st.query(f, s, 0, st.n, 1);
if(l != -INF){
if(f == a[i])
determined_side[i] = 1;
}
}
queries.pb({l, max(a[i], b[i]), i, -1});
queries.pb({r, max(a[i], b[i]), i, 1});
}
segsum ft(mx);
sort(queries.begin(), queries.end());
int pp = 0;
REP(i, t.size() + 1){
while(pp < queries.size() && ((queries[pp].x <= i) || (i == (int)t.size()))){ // ans queries
auto que = queries[pp];
int ans = ft.query(que.tl, mx, 0, ft.n, 1);
ans *= que.sign;
numflips[que.query_index] += ans;
pp++;
}
if(i == (int)t.size())
break;
ft.upd(t[i], 1);
}
ll sum = 0;
REP(i, n){
int side = determined_side[i];
side ^= (numflips[i] % 2);
if(side == 0)
sum += oa[i];
else
sum += ob[i];
}
cout << sum << "\n";
}
Compilation message
fortune_telling2.cpp: In constructor 'segmax::segmax(int, std::vector<int>&)':
fortune_telling2.cpp:19:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | if(i < init.size()){
| ~~^~~~~~~~~~~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:4:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
| ^
fortune_telling2.cpp:6:19: note: in expansion of macro 'FOR'
6 | #define REP(i, n) FOR(i, 0, n, 1)
| ^~~
fortune_telling2.cpp:123:5: note: in expansion of macro 'REP'
123 | REP(i, t.size() + 1){
| ^~~
fortune_telling2.cpp:124:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<main()::query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | while(pp < queries.size() && ((queries[pp].x <= i) || (i == (int)t.size()))){ // ans queries
| ~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
19532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
19532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
19532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
