Submission #1143660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143660		fryingduc	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	263 ms	13560 KiB

fortune_telling2

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 2e5 + 5;
const int N = 6e5 + 5;
int n, k, a[maxn], b[maxn], t[maxn];
int org_a[maxn], org_b[maxn];
int ord[maxn], que[maxn];
int tree[N << 2], bit[N];
int lst[maxn], flip[maxn];

void update(int pos, int val, int ind = 1, int l = 1, int r = k) {
  if(l == r) {
    tree[ind] = val;
    return;
  }
  int mid = (l + r) >> 1;
  if(pos <= mid) {
    update(pos, val, ind << 1, l, mid);
  } else {
    update(pos, val, ind << 1 | 1, mid + 1, r);
  }
  tree[ind] = max(tree[ind << 1], tree[ind << 1 | 1]);
}

void upd(int i, int val) {
  for(; i < N; i += i & (-i)) {
    bit[i] += val;
  }
}

int get(int i) {
  int ans = 0;
  for(; i > 0; i -= i & (-i)) {
    ans += bit[i];
  }
  return ans;
}

int get(int l, int r) {
  return l > r ? 0 : get(r) - get(l - 1);
}

int walk(int val, int ind = 1, int l = 1, int r = k) {
  if(l == r) {
    debug(val, l, r, tree[ind]);
    return (tree[ind] >= val ? l : l - 1);
  }
  int mid = (l + r) >> 1;
  if(tree[ind << 1 | 1] >= val) {
    return walk(val, ind << 1 | 1, mid + 1, r);
  }
  return walk(val, ind << 1, l, mid);
}

void solve() { 
  cin >> n >> k;
  vector<int> vec;
  for(int i = 1; i <= n; ++i) {
    cin >> a[i] >> b[i];
    org_a[i] = a[i], org_b[i] = b[i];
    vec.push_back(a[i]);
    vec.push_back(b[i]);
    ord[i] = i;
  }
  for(int i = 1; i <= k; ++i) {
    cin >> t[i];
    que[i] = i;
    vec.push_back(t[i]);
  }
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
  for(int i = 1; i <= n; ++i) {
    a[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin() + 1;
    b[i] = lower_bound(vec.begin(), vec.end(), b[i]) - vec.begin() + 1;
  }
  for(int i = 1; i <= k; ++i) {
    t[i] = lower_bound(vec.begin(), vec.end(), t[i]) - vec.begin() + 1;
  }
  sort(ord + 1, ord + n + 1, [](const int &x, const int &y) -> bool {
    return max(a[x], b[x]) < max(a[y], b[y]);
  });
  sort(que + 1, que + k + 1, [](const int &x, const int &y) -> bool {
    return t[x] < t[y];
  });
  int ptr = 1;
  for(int i = 1; i <= n; ++i) {
    while(ptr <= k and t[que[ptr]] < max(a[ord[i]], b[ord[i]])) {
      update(que[ptr], t[que[ptr]]);
      ++ptr;
    }
    lst[ord[i]] = walk(min(a[ord[i]], b[ord[i]]));
  }  
  iota(ord + 1, ord + n + 1, 1);
  sort(ord + 1, ord + n + 1, [](const int &x, const int &y) -> bool {
    return lst[x] > lst[y];
  });
  ptr = k;
  long long res = 0;
  for(int i = 1; i <= n; ++i) {
    while(ptr and ptr > lst[ord[i]]) {
      upd(t[ptr], 1);
      --ptr;
    }
    int t = get(max(a[ord[i]], b[ord[i]]), N - 1) & 1;
    if(a[ord[i]] < b[ord[i]] and lst[ord[i]] > 0) {
      t ^= 1;
    }
    res += (t == 0 ? org_a[ord[i]] : org_b[ord[i]]);
  }
  cout << res;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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