This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 1e9;
const int N = 2e5 + 50;
int n, k, T[N];
bool vis[N];
pair<pii, int> P[N];
vector<pii> fenmx[N];
int fen[N];
int getmx(int i) {
int id = 0;
for (; i > 0; i -= i&-i) {
while (vis[fenmx[i].back().S]) fenmx[i].pop_back();
if (fenmx[i].back().F > P[id].F.S) id = fenmx[i].back().S;
}
return id;
}
int get(int i) {
int out = fen[0];
for (; i > 0; i -= i&-i) {
out += fen[i];
}
return out;
}
void upd(int i, int x) {
if (!i) fen[i] += x;
else for (; i <= n; i += i&-i) {
fen[i] += x;
}
}
void solve() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
fenmx[i].push_back({0, 0});
}
for (int i = 1; i <= n; i++) {
cin >> P[i].F.F >> P[i].F.S;
P[i].S = (P[i].F.F > P[i].F.S);
if (P[i].S) swap(P[i].F.F, P[i].F.S);
}
sort(P+1, P+n+1);
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j += j&-j) {
fenmx[j].push_back({P[i].F.S, i});
}
}
for (int i = 1; i <= n; i++) {
sort(fenmx[i].begin(), fenmx[i].end());
}
for (int i = 1; i <= k; i++) {
cin >> T[i];
}
for (int i = k; i >= 1; i--) {
int id = upper_bound(P+1, P+n+1, mk(mk(T[i], inf), inf))-P-1;
int t = getmx(id);
while (P[t].F.S > T[i]) {
P[t].S = (get(t)^1)&1;
vis[t] = 1;
t = getmx(id);
}
upd(0, +1);
upd(id+1, -1);
}
int t = getmx(n);
while (t) {
P[t].S ^= (get(t)&1);
vis[t] = 1;
t = getmx(n);
}
ll ans = 0;
for (int i = 1; i <= n; i++) {
ans += (P[i].S? P[i].F.S: P[i].F.F);
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
solve();
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... |