#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 2e5+5;
const int M = 250;
const int mod = 1e9+7;
const ll base = 75;
const int inf = 1e9;
int m, n, t, b[N], d[N], lab[N], c[N];
int k, a[N], dp[N], lst[N], fe[N];
ll ans, tong;
vector<int> adj[N], g[N];
vector<int> vi;
string s[N];
bool vis[N];
bool cmp(const int& x, const int& y)
{
return d[x] > d[y];
}
void add(int id, int x)
{
for(; id; id -= id & -id)
fe[id] += x;
}
int get(int id)
{
int res = 0;
for(; id <= m; id += id & -id)res += fe[id];
return res;
}
struct IT
{
int n;
vector<int> st;
IT(int _n)
{
n = _n;
st.resize(n*4+4, 0);
}
void build(int id, int l, int r, int pos, int x)
{
if(l == r)
{
st[id] = max(x, st[id]);
return;
}
int mid = (l+r)>>1;
if(pos <= mid)build(id<<1, l, mid, pos, x);
else build(id<<1|1, mid+1, r, pos, x);
st[id] = max(st[id<<1], st[id<<1|1]);
}
void build(int pos, int x)
{
build(1, 1, n, pos, x);
}
int get(int id, int l, int r, int u, int v)
{
if(u <= l && r <= v)return st[id];
if(u > r || l > v)return 0;
int mid = (l+r)>>1;
return max(get(id<<1, l, mid, u, v), get(id<<1|1, mid+1, r, u, v));
}
int get(int l, int r)
{
return get(1, 1, n, l, r);
}
};
void sol()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++)cin >> a[i] >> b[i];
for(int i = 1; i <= m; i ++)
{
cin >> d[i];
vi.pb(d[i]);
}
sort(vi.begin(), vi.end());
vi.erase(unique(vi.begin(), vi.end()), vi.end());
IT it(m);
for(int i = m; i > 0; i --)
{
c[i] = lower_bound(vi.begin(), vi.end(), d[i]) - vi.begin() + 1;
it.build(c[i], i);
}
for(int i = 1; i <= n; i ++)
{
int l = lower_bound(vi.begin(), vi.end(), min(a[i], b[i])) - vi.begin() + 1;
int r = lower_bound(vi.begin(), vi.end(), max(a[i], b[i])) - vi.begin();
//cout << l <<" "<<r<<'\n';
if(l <= r)lst[i] = it.get(l, r);
adj[lst[i]].pb(i);
}
for(int i = m; i >= 0; i --)
{
for(int j: adj[i])
{
if(a[j] < b[j])swap(a[j], b[j]);
int r = upper_bound(vi.begin(), vi.end(), a[j]) - vi.begin();
k = get(r);
if(k&1)
{
ans += b[j];
//cout << b[j] <<" ";
}
else
{
//cout << a[j] <<" ";
ans += a[j];
}
//cout <<k<<" "<< r << '\n';
}
//cout << c[i] <<" "<< i << '\n';
if(i)add(c[i], 1);
}
cout << ans;
}
int main()
{
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
#define task "test"
if(fopen(task".inp", "r"))
{
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int test = 1;
//cin >> test;
while(test -- > 0)sol();
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:133:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
133 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:134:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
134 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
15948 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
15988 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
15948 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
15988 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
15948 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
15988 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
