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 <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#define ll long long
#define MAXN 200010
#define pii pair<int, int>
#define xx first
#define yy second
#define pb push_back
using namespace std;
int n, k, a[MAXN], b[MAXN], t[MAXN], last[MAXN];
ll cnt[MAXN];
ll ress[MAXN];
int bit[MAXN+5], seg[4*MAXN];
bool sw[MAXN];
pii c[MAXN];
vector<pii> tmp;
void build(int node, int l, int r)
{
if (l==r) { seg[node]=c[l].yy; return; }
int mid=l+(r-l)/2;
build(2*node, l, mid);
build(2*node+1, mid+1, r);
seg[node]=max(seg[2*node], seg[2*node+1]);
}
int maxQuery(int node, int l, int r, int levo, int desno)
{
if (levo>r || desno<l) return -1;
if (levo<=l && desno>=r) return seg[node];
int mid=l+(r-l)/2;
return max(maxQuery(2*node, l, mid, levo, desno),
maxQuery(2*node+1, mid+1, r, levo, desno));
}
void upd(int x, int val)
{
while (x<MAXN)
{
bit[x]+=val;
x+=x&(-x);
}
return;
}
int sum(int x)
{
int ret=0;
while (x)
{
ret+=bit[x];
x-=x&(-x);
}
return ret;
}
int main() {
cin>>n>>k;
for (int i=1; i<=n; i++) { cin>>a[i]>>b[i]; if (a[i]>b[i]) { sw[i]=true; swap(a[i], b[i]); } }
for (int i=1; i<=k; i++) cin>>t[i];
for (int i=1; i<=k; i++) { pii par={t[i], i}; c[i]=par; }
sort(c+1, c+k+1);
///for (int i=1; i<=k; i++) { cout<<c[i].xx<<" "<<c[i].yy<<endl; }
build(1, 1, k);
for (int i=1; i<=n; i++) {
pii minpar = {a[i], 0}, maxpar = {b[i], 0};
int l = distance(c + 1, lower_bound(c + 1, c + k + 1, minpar));
int r = distance(c + 1, lower_bound(c + 1, c + k + 1, maxpar));
r--;
l++; r++;
///cout<<i<<": "<<l<<" lr "<<r<<endl;
if (l > r) last[i] = 0;
else last[i] = maxQuery(1, 1, k, l, r);
}
for (int i=1; i<=n; i++) tmp.pb({last[i], i});
sort(tmp.begin(), tmp.end()/*, greater<pii>()*/);
///for (int i=0; i<tmp.size(); i++) cout<<tmp[i].xx<<" tmp "<<tmp[i].yy<<endl;
int j=tmp.size()-1;
for (int i=k; i>=0; i--)
{
///cout<<"i "<<i<<endl;
if (i) upd(t[i], 1);
while (j>=0 && tmp[j].xx==i) { /*cout<<i<<" ij "<<j<<endl;*/ cnt[tmp[j].yy]=sum(a[tmp[j].yy]-1); j--; }
///cout<<j<<" j"<<endl;
}
for (int i=1; i<=n; i++)
{
int kolko=k-last[i]-cnt[i];
if (last[i]==0 && sw[i]) swap(a[i], b[i]);
///cout<<i<<" "<<last[i]<<" "<<cnt[i]<<endl;
if (last[i]==0) { if (kolko%2) ress[i]=b[i]; else ress[i]=a[i]; }
else { if (kolko%2) ress[i]=a[i]; else ress[i]=b[i]; }
}
///for (int i=1; i<=n; i++) cout<<ress[i]<<" ";
///cout<<endl;
ll ans=0;
for (int i=1; i<=n; i++) ans+=ress[i];
cout<<ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |