| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1123384 | nuutsnoynton | 공장들 (JOI14_factories) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair < ll, ll>;
const ll N = 2e5 + 2;
struct S {
ll mx_ind, mx_val;
};
struct qr{
ll ans_ind, ind, val;
};
ll c[200004], Q[200005];
S ST[4 * N];
ll TR[32 * N];
void Build(ll p, ll lo, ll hi) {
if ( lo == hi) {
ST[p].mx_ind = lo;
ST[p].mx_val = c[lo];
return ;
}
ll mid = (lo + hi)/2;
Build(2 * p, lo, mid);
Build(2 * p + 1, mid + 1, hi);
if(ST[2 * p].mx_val > ST[2 * p + 1].mx_val) ST[p] = ST[2 *p];
else ST[p] = ST[2 * p + 1];
}
ll Find(ll p, ll lo, ll hi, ll l, ll r) {
if ( lo > r || l > hi) return 0;
if ( l <= lo && hi <= r) {
return ST[p].mx_val;
}
ll mid = (lo + hi)/2;
return max(Find(2 * p, lo, mid, l, r), Find(2 * p + 1, mid + 1, hi, l, r));
}
void Update(ll p, ll lo, ll hi, ll x, ll y) {
if (lo == hi) {
TR[p] += y;
return ;
}
ll mid = (lo + hi)/2;
if ( x <= mid) Update(2 * p, lo, mid, x, y);
else Update(2 * p + 1, mid + 1, hi, x, y);
TR[p] = TR[2 * p] + TR[2 * p + 1];
}
ll Sum(ll p, ll lo, ll hi, ll l,ll r) {
if ( lo > r || l > hi) return 0;
if ( l <= lo && hi <= r) {
return TR[p];
}
ll mid = (lo + hi)/2;
return Sum(2 * p, lo, mid, l, r) + Sum(2 * p + 1, mid + 1, hi, l, r);
}
bool cmp(qr A, qr B) {
return A.ind < B.ind;
}
map < ll, ll > mp, to, beck;
int main() {
ll n, q, i, x, ind, p, y, lo, hi;
cin >> n >> q;
ll a[n + 2], b[n + 2];
for (i =1; i <= n; i ++) {
cin>> a[i] >> b[i];
mp[a[i]] ++;
mp[b[i]] ++;
}
vector < pair < ll , ll > > v;
for (i = 1; i <= q; i ++) {
cin >> Q[i];
v.push_back({Q[i], i});
mp[Q[i]] ++;
}
ind = 1;
for ( auto R : mp) {
to[R.first] = ind;
beck[ind] = R.first;
ind ++;
}
for (i = 1; i <= n; i ++) a[i] = to[a[i]], b[i] = to[b[i]];
for (i = 1; i <= q; i ++) Q[i] = to[Q[i]];
sort(v.begin(), v.end());
for (i = 1; i <= q; i ++) {
c[i] = v[i - 1].second;
}
Build(1, 1, q);
vector < qr > queries;
for (i = 1; i <= n; i ++) {
x = a[i];
y = b[i];
if ( x > y) swap(x, y);
lo = lower_bound(v.begin(), v.end(), make_pair(x , 0ll)) - v.begin();
hi = lower_bound(v.begin(), v.end(), make_pair(y, 0ll)) - v.begin();
lo ++;
p = 0;
if ( lo <= hi) {
p= Find(1, 1, q, lo, hi);
a[i] = y;
b[i] = x;
}
p ++;
queries.push_back({i, p, y});
}
ll ans[N];
sort(queries.begin(), queries.end(), cmp);
// while(!queries.empty() && queries.back().ind == q + 1) {
// p = Sum(1, 1, 4e5, queries.back().val, 4e5);
// ans[queries.back().ans_ind] = p;
// queries.pop_back();
// }
if ( queries.back().ind == q + 1) while(1);
for (i = q ; i >= 1;i --) {
Update(1, 1, 4e5, Q[i], 1);
while(!queries.empty() && queries.back().ind == i) {
p = Sum(1, 1, 4e5, queries.back().val, 4e5);
ans[queries.back().ans_ind] = p;
queries.pop_back();
}
}
ll ans_sum = 0;
for (i = 1; i <= n; i ++) {
if ( ans[i] % 2 == 1) ans_sum += beck[b[i]];
else ans_sum += beck[a[i]];
}
cout << ans_sum << endl;
}