#include <bits/stdc++.h>
using namespace std;
template <class T> inline bool minn(T &A,T B){return A > B ? (A = B,1) : 0;}
template <class T> inline bool maxx(T &A,T B){return A < B ? (A = B,1) : 0;}
//#define int long long
#define task "c"
#define rep(i, n) for(int i = 0;i < n;++i)
#define FOR(i, l, r) for(int i = l; i <= r; ++i)
#define FOD(i, r, l) for(int i = r; i >= l; --i)
#define dem(x) __builtin_popcount(x)
#define endl '\n'
#define all(a) (a).begin(), (a).end()
#define pb emplace_back
#define SZ(x) (int)((x).size())
#define fi first
#define se second
typedef pair<int,int> ii;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};
//const int base = 311;
//const int mod = 1e9 + 7;
const int N = 2e5 + 5; //
int a[N], b[N], n, m, p[N], t[N];
long long res;
struct IT{
ii st[4*N];
int sum[4*N];
void build(int id = 1, int l = 1, int r = m){
if(l == r){
st[id] = {t[l], l};
return;
}
int mid = l + r >> 1;
build(id<<1, l, mid);
build(id<<1|1, mid+1, r);
st[id] = max(st[id<<1], st[id<<1|1]);
}
void add(int i, int id = 1, int l = 1, int r = m){
if(l == r){
st[id].fi = -1;
sum[id] = 1;
return;
}
int mid = l + r >> 1;
if(i <= mid)add(i, id<<1, l, mid);
else add(i, id<<1|1, mid+1, r);
st[id] = max(st[id<<1], st[id<<1|1]);
sum[id] = sum[id<<1] + sum[id<<1|1];
}
int pos(int x, int id = 1, int l = 1, int r = m){
if(l == r)return l;
int mid = l + r >> 1;
return st[id<<1|1].fi >= x ? pos(x, id<<1|1, mid+1, r) : pos(x, id<<1, l, mid);
}
int get(int u, int v, int id = 1, int l = 1, int r = m){
if(l > v or r < u)return 0;
if(u <= l && r <= v)return sum[id];
int mid = l + r >> 1;
return get(u, v, id<<1, l, mid) + get(u, v, id<<1|1, mid+1, r);
}
}seg;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
if(fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
// freopen(task".ans", "w", stdout);
}
cin >> n >> m;
FOR(i, 1, n){
cin >> a[i] >> b[i];
p[i] = i;
}
sort(p + 1, p + 1 + n, [&](int i, int j){
return max(a[i], b[i]) > max(b[i], b[j]);
});
FOR(i, 1, m)cin >> t[i];
seg.build();
FOR(i, 1, n){
int Max = max(a[p[i]], b[p[i]]);
int Min = min(a[p[i]], b[p[i]]);
while(seg.st[1].fi >= Max)seg.add(seg.st[1].se);
if(seg.st[1].fi >= Min){
int j = seg.pos(Min);
res += seg.get(j, m)&1 ? Min : Max;
continue;
}
res += seg.sum[1]&1 ? b[p[i]] : a[p[i]];
}
cout << res;
}
Compilation message
fortune_telling2.cpp: In member function 'void IT::build(int, int, int)':
fortune_telling2.cpp:33:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
33 | int mid = l + r >> 1;
| ~~^~~
fortune_telling2.cpp: In member function 'void IT::add(int, int, int, int)':
fortune_telling2.cpp:44:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
44 | int mid = l + r >> 1;
| ~~^~~
fortune_telling2.cpp: In member function 'int IT::pos(int, int, int, int)':
fortune_telling2.cpp:52:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
52 | int mid = l + r >> 1;
| ~~^~~
fortune_telling2.cpp: In member function 'int IT::get(int, int, int, int, int)':
fortune_telling2.cpp:58:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
58 | int mid = l + r >> 1;
| ~~^~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:66:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
66 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
21076 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
21076 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
21076 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
