#include <iostream>
#include <vector>
#include <ctime>
#include <algorithm>
using namespace std;
#define task "test"
#define bit(s, i) ((s >> i) & 1)
#define all(v) v.begin(), v.end()
#define ii pair <int, int>
#define vii vector<ii>
#define vi vector <int>
#define fi first
#define se second
#define ll long long
#define mp make_pair
#define eb emplace_back
#define pb push_back
void solve();
int32_t main()
{
if(fopen(task".inp", "r"))
{
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
double start = clock();
int tc = 1;
// cin >> tc;
while(tc--)
{
solve();
}
cerr << "Elapsed time: " << ((double)clock() - start) / CLOCKS_PER_SEC * 1000 << " ms";
}
const int mod = 1e9+7;
const int inf = 1e9;
const ll infll = 1e18;
const int N = 2e5+5;
int n, k;
ii a[N], t[N];
vi rar;
struct segTree
{
int st[N*12];
segTree()
{
fill(st+1, st+1+N*12, 1);
}
void upd(int x, int v, int id=1, int l=1, int r=N*3)
{
if(x>r or x<l) return;
if(l == r)
{
st[id] = v;
return;
}
int mid = (l + r) >> 1;
upd(x, v, id<<1, l, mid);
upd(x, v, id<<1|1, mid+1, r);
st[id] = max(st[id<<1], st[id<<1|1]);
}
int get(int u, int v, int id=1, int l=1, int r=N*3)
{
if(u>r or v<l) return 1;
if(u<=l and r<=v)
{
return st[id];
}
int mid = (l + r) >> 1;
return max(get(u, v, id<<1, l, mid), get(u, v, id<<1|1, mid+1, r));
}
} tree;
struct BIT
{
int f[3*N];
void upd(int id)
{
for(; id > 0; id -= id & -id) f[id] += 1;
}
int get(int id)
{
int ans = 0;
for(; id<3*N; id += id & -id) ans += f[id];
return ans;
}
} pos;
void solve()
{
cin >> n >> k;
for(int i = 1; i <= n; ++i)
{
cin >> a[i].fi >> a[i].se;
rar.eb(a[i].fi);
rar.eb(a[i].se);
}
for(int i = 1; i <= k; ++i)
{
cin >> t[i].fi; t[i].se = i;
rar.eb(t[i].fi);
}
sort(all(rar));
rar.erase(unique(all(rar)), rar.end());
for(int i = 1; i <= k; ++i)
{
t[i].fi = upper_bound(all(rar), t[i].fi) - rar.begin();
tree.upd(t[i].fi, i);
}
sort(t+1, t+1+k, [] (ii x, ii y) {return x.fi < y.fi;});
sort(a+1, a+1+n, [] (ii x, ii y) {return max(x.fi, x.se) > max(y.fi, y.se);});
int id = k;
ll tot = 0;
for(int i = 1; i <= n; ++i)
{
a[i].fi = upper_bound(all(rar), a[i].fi) - rar.begin();
a[i].se = upper_bound(all(rar), a[i].se) - rar.begin();
int x = min(a[i].fi, a[i].se), y = max(a[i].fi, a[i].se);
while(t[id].fi >= y and id > 0)
{
pos.upd(t[id].se);
id--;
}
int last = tree.get(x, y-1);
int tmp = pos.get(last);
tot += (tmp & 1) ? rar[a[i].se-1] : rar[a[i].fi-1];
}
cout << tot;
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/
Compilation message
fortune_telling2.cpp: In function 'int32_t main()':
fortune_telling2.cpp:27:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
27 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:28:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
28 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
25692 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
25692 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
25692 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
