Submission #505753

#	Time	Username	Problem	Language	Result	Execution time	Memory
505753		Abrar_Al_Samit	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	35 / 100	2561 ms	262148 KiB

fortune_telling2

#include<bits/stdc++.h>
using namespace std;
const int MX = 200005;
const int uMX = 600006;

int n, k;
int a[MX], b[MX];
int ops[MX];
map<int,int>HASH;
set<int>store[uMX*4];

void enlist(int l, int r, int L, int R, int id, int v) {
  if(l>=L && r<=R) {
    store[v].insert(id);
    return;
  }
  if(l>R || r<L) return;
  int m = (l+r)/2;
  enlist(l, m, L, R, id, v*2);
  enlist(m+1, r, L, R, id, v*2+1);
}
void delist(int l, int r, int L, int R, int id, int v) {
  if(l>=L && r<=R) {
    store[v].erase(id);
    return;
  }
  if(l>R || r<L) return;
  int m = (l+r)/2;
  delist(l, m, L, R, id, v*2);
  delist(m+1, r, L, R, id, v*2+1);
}
vector<int>st(uMX*4);
void upd(int l, int r, int dest, int v) {
  if(l==r) {
    ++st[v];
    return;
  }
  int m = (l+r)/2;
  if(dest<=m) upd(l, m, dest, v*2);
  else upd(m+1, r, dest, v*2+1);
  st[v] = st[v*2]+st[v*2+1];
}
int getCount(int l, int r, int L, int R, int v) {
  if(l>=L && r<=R) {
    return st[v];
  } 
  if(l>R || r<L) return 0;
  int m = (l+r)/2;
  return getCount(l, m, L, R, v*2) + getCount(m+1, r, L, R, v*2+1);
}
set<int>get(int l, int r, int p, int v) {
  set<int>ret = store[v];
  if(l==r) return ret;
  int m = (l+r)/2;
  set<int>got;
  if(p<=m) {
    got = get(l, m, p, v*2);
  } else {
    got = get(m+1, r, p, v*2+1);
  }
  while(!got.empty()) {
    ret.insert(*got.begin());
    got.erase(got.begin());
  }
  return ret;
}
void PlayGround() {
  cin >> n >> k;
  for(int i=1; i<=n; ++i) {
    cin >> a[i] >> b[i];
    HASH[a[i]] = HASH[b[i]] = 0;
  }
  for(int i=1; i<=k; ++i) {
    cin >> ops[i];
    HASH[ops[i]] = i;
  }
  int tag = 1;
  for(auto &p : HASH) {
    p.second = tag++;
  } //end of HASH stuffs


  long long ans = 0;
  set<int>done;
  for(int i=1; i<=n; ++i) {
    if(a[i]==b[i]) {
      done.insert(i);
      ans += a[i];
      continue;
    }
    int mn = a[i], mx = b[i];
    if(mn>mx) swap(mn, mx);
    enlist(1, uMX-1, HASH[mn], HASH[mx]-1, i, 1);
  }
  for(int i=k; i>0; --i) {
    set<int>cur = get(1, uMX-1, HASH[ops[i]], 1);
    for(int j : cur) {
      int mn = a[j], mx = b[j];
      if(mn>mx) swap(mn, mx);
      delist(1, uMX-1, HASH[mn], HASH[mx]-1, j, 1);
      done.insert(j);
      int cnt = getCount(1, uMX-1, HASH[mx], uMX-1, 1);
      ans += (cnt&1)?mn:mx;
    }
    upd(1, uMX-1, HASH[ops[i]], 1);
  }

  for(int i=1; i<=n; ++i) if(!done.count(i)) {
    int mn = a[i], mx = b[i];
    if(mn>mx) swap(mn, mx);
    int cnt = getCount(1, uMX-1, HASH[mx], uMX-1, 1);
    ans += (~cnt&1)?a[i]:b[i];
  }
  cout << ans << endl;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

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