Submission #304654

#	Time	Username	Problem	Language	Result	Execution time	Memory
304654		AlexPop28	Fortune Telling 2 (JOI14_fortune_telling2)	C++11	100 / 100	394 ms	35424 KiB

fortune_telling2

#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

template<class T> void Max(T &a, const T &b) { a = max(a, b); }

struct SegmTree {
  int n;
  vector<int> t;
  SegmTree(int n_) : n(n_), t(2 * n, -1) {}
  
  void Update(int pos, int val) {
    for (Max(t[pos += n], val); pos /= 2; ) {
      t[pos] = max(t[2 * pos], t[2 * pos + 1]);
    }
  }

  int Query(int l, int r) {
    int ans = -1;
    for (l += n, r += n; l < r; l /= 2, r /= 2) {
      if (l & 1) Max(ans, t[l++]);
      if (r & 1) Max(ans, t[--r]);
    }
    return ans;
  }
};

struct Fenwick {
  int n;
  vector<int> t;
  Fenwick(int n_) : n(n_), t(n + 1) {}
  inline int lsb(int x) {
    return x & -x;
  }
  void Update(int pos, int val) {
    for (++pos; pos; pos -= lsb(pos))
      t[pos] += val;
  }
  int Query(int pos) {
    int ans = 0;
    for (++pos; pos <= n; pos += lsb(pos))
      ans += t[pos];
    return ans;
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n, k; cin >> n >> k;
  vector<int> all;
  vector<vector<int>> v(n, vector<int>(2));
  for (int i = 0; i < n; ++i) {
    int a, b; cin >> a >> b;
    v[i] = {a, b};
    all.emplace_back(a);
    all.emplace_back(b);
  }

  vector<int> qrs(k);
  for (int i = 0; i < k; ++i) {
    int x; cin >> x;
    all.emplace_back(x);
    qrs[i] = x;
  }

  sort(all.begin(), all.end());
  all.erase(unique(all.begin(), all.end()), all.end());

  auto Norm = [&](int x) {
    return lower_bound(all.begin(), all.end(), x) - all.begin();
  };

  SegmTree st(all.size());
  for (int i = 0; i < k; ++i) {
    qrs[i] = Norm(qrs[i]);
    st.Update(qrs[i], i);
  }

  vector<vector<pair<int, int>>> query(k + 1);
  for (int i = 0; i < n; ++i) {
    int l = v[i][0], r = v[i][1];
    if (l > r) swap(l, r);
    l = Norm(l), r = Norm(r);

    int pos = st.Query(l, r) + 1;
    query[pos].emplace_back(i, r);
    if (pos > 0 && v[i][0] < v[i][1]) swap(v[i][0], v[i][1]);

//    dbg() name(i) name(v[i][0]) name(v[i][1]) name(pos) endl;
  }
  
  int64_t ans = 0;
  Fenwick fw(all.size());
  for (int i = k; i >= 0; --i) {
    if (i != k)
      fw.Update(qrs[i], +1);
    for (auto &p : query[i]) {
      int idx, r; tie(idx, r) = p;
      int cnt = fw.Query(r);
      ans += v[idx][cnt % 2];
//      dbg() name(idx) name(cnt) name(v[idx][cnt % 2]) endl;
    }
  }

  cout << ans << endl;
}

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