Submission #505167

#	Time	Username	Problem	Language	Result	Execution time	Memory
505167		Abrar_Al_Samit	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	0 / 100	31 ms	28640 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, iHASH;
vector<int>mst[MX*4], imst(uMX*4);
//mst ->index to value
//imst ->value to index
//HASH ->HASH value of some bigger value
//iHASH ->index of some HASH value

vector<int>merge(vector<int>A, vector<int>B) {
  vector<int>ret;
  int p = 0, q = 0;
  int N = A.size(), M = B.size();
  while(p<N && q<M) {
    if(A[p]<B[q]) {
      ret.push_back(A[p++]);
    } else {
      ret.push_back(B[q++]);
    }
  }
  while(p<N) ret.push_back(A[p++]);
  while(q<M) ret.push_back(B[q++]);
  return ret;
}
void Build(int l, int r, int v) { //mst
  if(l==r) {
    mst[v].push_back(ops[l]);
    return;
  }
  int m = (l+r)/2;
  Build(l, m, v*2);
  Build(m+1, r, v*2+1);
  mst[v] = merge(mst[v*2], mst[v*2+1]);
}
void Build2(int l, int r, int v) { //imst
  if(l==r) {
    if(iHASH.count(l)) {
      imst[v] = iHASH[l];
    } else {
      imst[v] = -1;
    }
    return;
  }
  int m = (l+r)/2;
  Build2(l, m, v*2);
  Build2(m+1, r, v*2+1);
  imst[v] = max(imst[v*2], imst[v*2+1]);
}
int q2(int l, int r, int L, int R, int v) {
  if(l>=L && r<=R) {
    return imst[v];
  } else if(l>R || r<L) return -1;
  
  int m = (l+r)/2;
  return max(q2(l, m, L, R, v*2), q2(m+1, r, L, R, v*2+1));
}
int q(int l, int r, int L, int R, int lb, int v) {
  if(l>=L && r<=R) {
    return mst[v].end()-lower_bound(mst[v].begin(), mst[v].end(), lb);
  }
  if(l>R || r<L) return 0;
  int m = (l+r)/2;
  return q(l, m, L, R, lb, v*2) + q(m+1, r, L, R, lb, v*2+1);
}
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) {
    if(p.second) iHASH[tag] = p.second;
    p.second = tag++;
  } //end of HASH stuffs



  Build(1, k, 1);
  Build2(1, uMX-1, 1);

  //final processing
  long long ans = 0;
  for(int i=1; i<=n; ++i) {
    if(a[i]==b[i]) {
      ans += a[i];
      continue;
    }
    int mx = a[i], mn = b[i];
    if(mx<mn) swap(mx, mn);
    int yellow = q2(1, uMX-1, HASH[mn], HASH[mx]-1, 1);
    int l;
    if(yellow==-1) l = 1;
    else l = yellow+1;
    int cnt = q(1, k, l, k, HASH[mx], 1);
    if(yellow==-1) {
      ans += (cnt&1)?b[i]:a[i];
    } else {
      ans += (cnt&1)?mn:mx;
    }
  }

  cout << ans << endl;



  // cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

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