Submission #852815

#	Time	Username	Problem	Language	Result	Execution time	Memory
852815		epicci23	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	0 / 100	5 ms	21084 KiB

fortune_telling2

#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl "\n" 
#define int long long
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

const int N = 2e5 + 5;

int n,k;
array<int,2> ar[N];

struct SegT{
  vector<int> seg;
  SegT(int n){seg.assign(4*n+5,0);}

  void update(int rt,int l,int r,int ind,int u){
  	if(r<ind || l>ind) return;
  	if(l==r){
  	 seg[rt]=max(seg[rt],u);
  	 return;
  	}
  	int m=(l+r)/2;
  	update(rt*2,l,m,ind,u);update(rt*2+1,m+1,r,ind,u);
  	seg[rt]=max(seg[rt*2],seg[rt*2+1]);
  }

  int query(int rt,int l,int r,int gl,int gr){
  	if(r<gl || l>gr) return 0;
  	if(l>=gl && r<=gr) return seg[rt];
  	int m=(l+r)/2;
  	return max(query(rt*2,l,m,gl,gr),query(rt*2+1,m+1,r,gl,gr));
  }
};

vector<int> seg[4*N];
int xd[N];

void build(int rt,int l,int r){
  if(l==r){
  	seg[rt].pb(xd[l]);
  	return;
  }
  int m=(l+r)/2;
  build(rt*2,l,m);build(rt*2+1,m+1,r);
  int p1=0,p2=0;
  while(p1<sz(seg[rt*2]) && p2<sz(seg[rt*2+1])){
  	if(seg[rt*2][p1] <= seg[rt*2+1][p2]) seg[rt].pb(seg[rt*2][p1++]);
  	else seg[rt].pb(seg[rt*2+1][p2++]);
  }

  while(p1<sz(seg[rt*2])) seg[rt].pb(seg[rt*2][p1++]);
  while(p2<sz(seg[rt*2+1])) seg[rt].pb(seg[rt*2+1][p2++]);
}

int query(int rt,int l,int r,int gl,int gr,int x){
   if(r<gl || l>gr || gl>gr || l>r) return 0;
   if(l>=gl && r<=gr){
   	 int lol=lower_bound(all(seg[rt]),x)-seg[rt].begin();
   	 return sz(seg[rt])-lol;
   }
   int m=(l+r)/2;
   return query(rt*2,l,m,gl,gr,x) + query(rt*2+1,m+1,r,gl,gr,x);
}

void solve(){

  cin >> n >> k;
  map<int,int> mp;
  for(int i=1;i<=n;i++){
  	int a,b;
  	cin >> a >> b;
  	ar[i]={a,b};
  	mp[a]=mp[b]=mp[a-1]=mp[b-1]=1;
  }
  
  
  for(int i=1;i<=k;i++){ 
  	cin >> xd[i];
  	mp[xd[i]]=1;
  }
  
  int p=0;
  for(auto x:mp) mp[x.first]=++p;
  
  SegT Seg(p);

  for(int i=1;i<=k;i++) Seg.update(1,1,p,mp[xd[i]],i);

  build(1,1,k);
  
  int ans=0;

  for(int i=1;i<=n;i++){
    if(ar[i][0]==ar[i][1]){
      ans+=ar[i][0];
      continue;
    }
    int ok=0;
    if(ar[i][0]>ar[i][1]){
       swap(ar[i][0],ar[i][1]);
       ok++;
    }
    int hm=Seg.query(1,1,p,mp[ar[i][0]],mp[ar[i][1]-1]);
    ok+=query(1,1,k,hm+1,k,ar[i][1]);
    if(ok&1) ans+=ar[i][1];
    else ans+=ar[i][0];
  }

  cout << ans << endl;
}

int32_t main(){

  cin.tie(0); ios::sync_with_stdio(0);
  
  int t=1;//cin >> t;
  while(t--) solve();

  return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 31
• Subtask 3: 0 / 65