Submission #1233724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233724		lopkus	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	369 ms	39780 KiB

fortune_telling2

#include <bits/stdc++.h>

#define int int64_t

const int N = 1e6 + 5;

struct segtree{
    int t[4 * N] = {0};
    int query(int v, int tl, int tr, int l, int r) {
        if(tl > r || tr < l) {
            return 0;
        }
        if(tl >= l && tr <= r) {
            return t[v];
        }
        int tm = (tl + tr) / 2;
        return std::max(query(v * 2, tl, tm, l, r), query(v * 2 + 1, tm + 1, tr, l, r));
    }
    void update(int v, int tl, int tr, int index, int value) {
        if(tl == tr) {
            t[v] = value;
        }
        else {
            int tm = (tl + tr) / 2;
            if(index <= tm) {
                update(v * 2, tl, tm, index, value);
            }
            else {
                update(v * 2 + 1, tm + 1, tr, index, value);
            }
            t[v] = std::max(t[v * 2], t[v * 2 + 1]);
        }
    }
}seg;

struct fenw {
  int t[2 * N];
  void update(int i, int v) {
    for(; i < N; i += i & - i) {
      t[i] += v;
    }
  }
  int query(int i) {
    int ans = 0;
    for(; i > 0; i -= i & - i) {
      ans += t[i];
    }
    return ans;
  }
  int query(int l, int r) {
    return query(r) - query(l - 1);
  }
}fenw;

signed main() {
  int n, q;
  std::cin >> n >> q;
  std::vector<int> a(n + 1), b(n + 1);
  for(int i = 1; i <= n; i++) {
    std::cin >> a[i] >> b[i];
  }
  std::vector<int> x(q + 1);
  for(int i = 1; i <= q; i++) {
    std::cin >> x[i];
  }
  std::vector<int> t(n + 1);
  for(int i = 1; i <= n; i++) {
    if(a[i] > b[i]) {
      t[i] = 1;
      std::swap(a[i], b[i]);
    }
  }
  std::vector<int> compres;
  for(int i = 1; i <= n; i++) {
    compres.push_back(a[i]);
    compres.push_back(b[i]);
  }
  for(int i = 1; i <= q; i++) {
    compres.push_back(x[i]);
  }
  std::sort(compres.begin(), compres.end());
  compres.erase(unique(compres.begin(), compres.end()), compres.end());
  std::vector<int> fa(n + 1);
  std::vector<int> fb(n + 1);
  std::vector<int> fx(q + 1);
  for(int i = 1; i <= n; i++) {
    fa[i] = lower_bound(compres.begin(), compres.end(), a[i]) - compres.begin() + 1;
    fb[i] = lower_bound(compres.begin(), compres.end(), b[i]) - compres.begin() + 1;
  }
  for(int i = 1; i <= q; i++) {
    fx[i] = lower_bound(compres.begin(), compres.end(), x[i]) - compres.begin() + 1;
  }
  for(int i = 1; i <= q; i++) {
    seg.update(1, 1, N, fx[i], i);
  }
  std::vector<std::array<int, 2>> query[q + 1];
  for(int i = 1; i <= n; i++) {
    int pos = seg.query(1, 1, N, fa[i], fb[i] - 1);
    if(pos != 0) {
      t[i] = 1;
    }
    pos += 1;
    if(pos <= q)
      query[pos].push_back({fb[i], i});
  }
  for(int i = q; i >= 1; i--) {
    fenw.update(fx[i], 1);
    for(auto [value, pos] : query[i]) {
      t[pos] += fenw.query(value, N);
    }
  }
  int ans = 0;
  for(int i = 1; i <= n; i++) {
    ans += (t[i] % 2 == 0 ? a[i] : b[i]);
  }
  std::cout << ans;
}

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