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;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define F first
#define S second
#define pb push_back
#define endl '\n'
#define Mp make_pair
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << endl;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("tests.in" , "r" , stdin) ;
ll mod = 1e9+7;
const int N = 6e5+23;
int seg[4*N], fen[N];
int a[N], b[N], t[N];
vector<int> in[N];
ll ans;
int n, k, m;
void upd(int i, int x, int l=1, int r=m+1, int ind=0){
if(r-l==1) {
seg[ind]=x;
return;
}
int mid=(r+l)>>1;
if(i<mid) upd(i, x, l, mid, 2*ind+1);
else upd(i, x, mid, r, 2*ind+2);
seg[ind]=max(seg[2*ind+1], seg[2*ind+2]);
}
int get(int lx, int rx, int l=1, int r=m+1, int ind=0){
if(lx>=r || rx<=l) return 0;
if(lx<=l && rx>=r) return seg[ind];
int mid=(r+l)>>1;
return max(get(lx, rx, l, mid, 2*ind+1), get(lx, rx, mid, r, 2*ind+2));
}
void uupd(int x, int v){
for(; x<N; x+=x&-x) fen[x]+=v;
}
int gget(int x){
int ans=0;
for(; x>0; x-=x&-x) ans+=fen[x];
return ans;
}
int suff(int i){
return gget(N-1)-gget(i-1);
}
int main()
{
fast_io
vector<int> vec;
cin>>n>>k;
for (int i=0; i<n; i++) {
cin>>a[i]>>b[i];
vec.pb(a[i]); vec.pb(b[i]);
}
t[0]=1;
for (int i=1; i<=k; i++) {
cin>>t[i];
vec.pb(t[i]);
}
sort(all(vec)); vec.resize(unique(all(vec))-vec.begin());
m=vec.size();
for (int i=1; i<=k; i++){
t[i]=lower_bound(all(vec), t[i])-vec.begin()+1;
upd(t[i], i);
}
for (int i=0; i<n; i++){
a[i]=lower_bound(all(vec), a[i])-vec.begin()+1;
b[i]=lower_bound(all(vec), b[i])-vec.begin()+1;
int num=get(min(a[i], b[i]), max(a[i], b[i]));
if(num && b[i]>a[i]) swap(a[i], b[i]);
in[num].pb(i);
}
for (int i=k; i>=0; i--){
for (int j: in[i]){
if(suff(max(a[j], b[j]))&1) swap(a[j], b[j]);
ans+=vec[a[j]-1];
}
uupd(t[i], 1);
}
cout<<ans<<endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |