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;
using LL = long long;
const int MOD = (int)1e9 + 7;
const int NS = (int)6e5 + 4;
int N, k;
int a[NS], b[NS];
int t[NS];
vector<int> srt;
int last[NS];
struct Data{
int pos, mn, num;
bool operator<(const Data&r)const{
return pos > r.pos;
}
}que[NS];
int seg[NS * 4];
void push(int num, int s, int e, int pos, int val){
if(pos < s || pos > e) return;
if(s == e){
seg[num] = val;
return;
}
push(num * 2, s, (s + e) / 2, pos, val), push(num * 2 + 1, (s + e) / 2 + 1, e, pos, val);
seg[num] = max(seg[num * 2], seg[num * 2 + 1]);
}
int get(int num, int s, int e, int fs, int fe){
if(fe < s || fs > e || fs > fe) return 0;
if(s >= fs && e <= fe){
return seg[num];
}
return max(get(num * 2, s, (s + e) / 2, fs, fe), get(num * 2 + 1, (s + e) / 2 + 1, e, fs, fe));
}
struct fenwick{
vector < int > fenw;
int N;
fenwick(){}
fenwick(int n):N(n){
fenw.resize(N);
}
void push(int x, int val){
for(int i = x; i < N; i += (i & -i)){
fenw[i] += val;
}
}
int get(int x){
int rv = 0;
for(int i = x; i; i -= (i & -i)){
rv += fenw[i];
}
return rv;
}
}fen(NS);
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> k;
for(int i = 1; i <= N; ++i){
cin >> a[i] >> b[i];
srt.push_back(a[i]), srt.push_back(b[i]);
}
for(int i = 1; i <= k; ++i){
cin >> t[i];
srt.push_back(t[i]);
}
sort(srt.begin(), srt.end());
srt.erase(unique(srt.begin(), srt.end()), srt.end());
for(int i = 1; i <= N; ++i){
a[i] = lower_bound(srt.begin(), srt.end(), a[i]) - srt.begin() + 1;
b[i] = lower_bound(srt.begin(), srt.end(), b[i]) - srt.begin() + 1;
}
for(int i = 1; i <= k; ++i){
t[i] = lower_bound(srt.begin(), srt.end(), t[i]) - srt.begin() + 1;
last[t[i]] = i;
}
for(int i = 1; i <= (int)srt.size(); ++i){
push(1, 1, (int)srt.size(), i, last[i]);
}
for(int i = 1; i <= N; ++i){
int mn = min(a[i], b[i]), mx = max(a[i], b[i]);
int pos = get(1, 1, (int)srt.size(), mn, mx - 1);
que[i].pos = pos + 1, que[i].mn = mx, que[i].num = i;
}
sort(que + 1, que + N + 1);
reverse(que + 1, que + N + 1);
int j = N;
LL ans = 0;
for(int i = k; i >= 1; --i){
while(j && que[j].pos > i){
// cout << que[j].pos << ' ' << que[j].mn << ' ' << que[j].num << endl;
int flip = fen.get((int)srt.size()) - fen.get(que[j].mn - 1);
if(a[que[j].num] >= b[que[j].num]){
if(flip % 2){
ans += srt[b[que[j].num] - 1];
}
else{
ans += srt[a[que[j].num] - 1];
}
}
else{
if(flip % 2){
ans += srt[a[que[j].num] - 1];
}
else{
ans += srt[b[que[j].num] - 1];
}
}
--j;
// cout << ans << endl;
}
fen.push(t[i], 1);
}
while(j){
// cout << que[j].pos << ' ' << que[j].mn << ' ' << que[j].num << endl;
int flip = fen.get((int)srt.size()) - fen.get(que[j].mn - 1);
if(a[que[j].num] >= b[que[j].num]){
if(flip % 2){
ans += srt[b[que[j].num] - 1];
}
else{
ans += srt[a[que[j].num] - 1];
}
}
else{
if((flip % 2 && que[j].pos > 1) || (flip % 2 == 0 && que[j].pos == 1)){
ans += srt[a[que[j].num] - 1];
}
else{
ans += srt[b[que[j].num] - 1];
}
}
--j;
// cout << ans << endl;
}
cout << ans;
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... |