/*
SOLUTION : For each item we calculate separately. Separate for each number the queries into 3 regions. Anything
in middle region basically keeps higher->higher and lower->higher. so find last region-type-2. count #region-typ
e-3 after that. (region-type-1 has no effect). Also, take acnt of the initial swap.
*/
#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <complex>
#include <stack>
#include <set>
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double>
#define ld long double
#define pld pair<ld,ld>
#define iii pair<ii,int>
const ld INF = 1e9+10;
using namespace std;
const int MAXN = 1000*100*2+10;
const int MAXVAL = 1e9+10;
struct Node{
Node* left;
Node* right;
int val;
Node(int v){
left = right = NULL;
val = v;
}
};
struct MaxSegtree{
Node* head;
inline void expand(Node* node){
if(node->left == NULL)node->left = new Node(-1);
if(node->right == NULL)node->right = new Node(-1);
}
void update(Node* node,int ss,int se,int i,int val){
if(i < ss or i > se)return;
expand(node);
if(ss == se){
node->val = val;
return;
}
int mid = (ss+se)/2;
update(node->left,ss,mid,i,val);
update(node->right,mid+1,se,i,val);
node->val = max(node->left->val,node->right->val);
}
int get(Node* node,int ss,int se,int l,int r){
if(node == NULL)return -1;
if(l > se or ss > r)return -1;
if(l <= ss and se <= r)return node->val;
int mid = (ss+se)/2;
return max(get(node->left,ss,mid,l,r),get(node->right,mid+1,se,l,r));
}
MaxSegtree(){
head = new Node(-1);
}
};
struct SumSegtree{
Node* head;
inline void expand(Node* node){
if(node->left == NULL)node->left = new Node(0);
if(node->right == NULL)node->right = new Node(0);
}
void update(Node* node,int ss,int se,int i,int val){
if(i < ss or i > se)return;
expand(node);
if(ss == se){
node->val += val;
return;
}
int mid = (ss+se)/2;
update(node->left,ss,mid,i,val);
update(node->right,mid+1,se,i,val);
node->val = (node->left->val + node->right->val);
}
int get(Node* node,int ss,int se,int l,int r){
if(node == NULL)return 0;
if(l > se or ss > r)return 0;
if(l <= ss and se <= r)return node->val;
int mid = (ss+se)/2;
return (get(node->left,ss,mid,l,r) + get(node->right,mid+1,se,l,r));
}
SumSegtree(){
head = new Node(0);
}
};
int ans[MAXN];
int main(){
int n,k;
cin >> n >> k;
vector<iii> all;
FOR(i,n){
int a,b;
cin >> a >> b;
if(b>a){
swap(a,b);
ans[i] = 1;
}else{
ans[i] = 0;
}
all.pb({{a,b},i});
}
sort(all.begin(), all.end());
MaxSegtree mst;
SumSegtree sst;
vector<ii> t;
FOR(i,k){
int x;
cin >> x;
t.pb({x,i});
mst.update(mst.head,0,MAXVAL,x,i);
}
sort(t.begin(), t.end());
reverse(all.begin(), all.end());
reverse(t.begin(), t.end());
int ptr = 0;
for(auto e : all){
while(ptr < (int)t.size() and t[ptr].ff >= e.ff.ff){
sst.update(sst.head,0,MAXVAL,t[ptr].ss,1);
ptr++;
}
int lst = 1 + mst.get(mst.head,0,MAXVAL,e.ff.ss,e.ff.ff-1);
ans[e.ss] += sst.get(sst.head,0,MAXVAL,lst,MAXVAL-2);
}
ll sum = 0;
for(auto e:all){
if(ans[e.ss]%2 == 0){
sum += e.ff.ff;
}else{
sum += e.ff.ss;
}
}
cout << sum << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
1788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
1788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
1788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
