#include "bits/stdc++.h"
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ff first
#define ss second
using namespace std;
const int N = 1e6 + 10;
int st[4 * N];
void update(int index, int l, int r, int val, int pos)
{
if(l > r || l > pos || r < pos) return;
if(l == r) { st[index] = val; return; }
int mid = (l + r) / 2;
update(index * 2, l, mid, val, pos); update(index * 2 + 1, mid + 1, r, val, pos);
st[index] = max(st[index * 2], st[index * 2 + 1]);
}
int get(int index, int l, int r, int L, int R)
{
if(l > r || l > R || r < L) return 0;
if(l >= L && r <= R) return st[index];
int mid = (l + r) / 2;
return max(get(index * 2, l, mid, L, R), get(index * 2 + 1, mid + 1, r, L, R));
}
void upd(int index, int l, int r, int val, int pos)
{
if(l > r || l > pos || r < pos) return;
if(l == r) { st[index] = val; return; }
int mid = (l + r) / 2;
upd(index * 2, l, mid, val, pos); upd(index * 2 + 1, mid + 1, r, val, pos);
st[index] = st[index * 2] + st[index * 2 + 1];
}
int gt(int index, int l, int r, int L, int R)
{
if(l > r || l > R || r < L) return 0;
if(l >= L && r <= R) return st[index];
int mid = (l + r) / 2;
return gt(index * 2, l, mid, L, R) + gt(index * 2 + 1, mid + 1, r, L, R);
}
bool comp(pair < pair < int , int > , int > a, pair < pair < int , int > , int > b)
{
return a.ss > b.ss;
}
// long long solve(int& n, int& k, vector < pair < pair < int , int > , int > >& vp, vector < int >& t)
int main()
{
FAST;
int n, k; cin >> n >> k;
vector < pair < pair < int , int > , int > > vp(n);
for(int i = 0; i < n; i++)
{
cin >> vp[i].ff.ff >> vp[i].ff.ss;
}
vector < int > t(k);
for(int i = 0; i < k; i++)
{
cin >> t[i];
update(1, 1, N - 10, i + 1, t[i]);
}
for(int i = 0; i < n; i++) vp[i].ss = get(1, 1, N - 10, min(vp[i].ff.ff, vp[i].ff.ss) , max(vp[i].ff.ff, vp[i].ff.ss) - 1) - 1;
// for(auto it : vp) cout << it.ss << " ";
// cout << "!\n";
sort(begin(vp), end(vp), comp);
for(int i = 0; i < k; i++) update(1, 1, N - 10, 0, t[i]);
int j = k - 1;
long long ans = 0;
for(int i = 0; i < n; i++)
{
while(j > vp[i].ss) { upd(1, 1, N - 10, 1, t[j]); j--; }
int trn = gt(1, 1, N - 10, max(vp[i].ff.ff, vp[i].ff.ss), N - 10);
// cout << " { { " << vp[i].ff.ff << " , " << vp[i].ff.ss << " } , " << vp[i].ss << " } -> ";
// cout << "number of flips: " << trn << "\n";
bool a = false;
if(vp[i].ff.ff > vp[i].ff.ss)
{
if(trn % 2) a = !a;
}
else
{
a = (j != -1); // true -> b, false -> a
if(trn % 2) a = !a;
}
ans += (a ? vp[i].ff.ss : vp[i].ff.ff);
}
cout << ans << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |