Submission #728218

#	Time	Username	Problem	Language	Result	Execution time	Memory
728218		jampm	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	4 / 100	3067 ms	2516 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using ll = long long int;
#define all(a) a.begin(), a.end()
const int Mxn = 6e5 + 2;

struct segtree_sum {
  vector<int> segs;
  segtree_sum() {segs.assign(Mxn<<1, 0);}
  void upd(int i, int x) {
    i += Mxn; segs[i] += x;
    for (i >>= 1; i; i >>= 1) {
      segs[i] = segs[i<<1] + segs[i<<1|1];
    }
  }
  int query(int l, int r, int ans = 0) {
    for (l += Mxn, r += Mxn + 1; l < r; l >>= 1, r >>= 1) {
      if (l&1) ans += segs[l++];
      if (r&1) ans += segs[--r];
    }
    return ans;
  }
};

struct segtree_max {
  vector<int> segs;
  segtree_max() {segs.assign(Mxn<<1, -1);}
  void upd(int i, int x) {
    i += Mxn; segs[i] = x;
    for (i >>= 1; i; i >>= 1) {
      segs[i] = max(segs[i<<1], segs[i<<1|1]);
    }
  }
  int query(int l, int r, int ans = -1) {
    for (l += Mxn, r += Mxn + 1; l < r; l >>= 1, r >>= 1) {
      if (l&1) ans = max(segs[l++], ans);
      if (r&1) ans = max(segs[--r], ans);
    }
    return ans;
  }
};

struct query {
  int idx, sufix, val;
  bool operator<(const query & X) {return sufix > X.sufix;}
};

//stress test brute force
ll brute_force(ll n, ll k, vector<pii> A, vector<int> B, ll ans = 0, ll idx = 0) {
  ll card[2][n], oper[k];
  for (int i = 0; i < n; i++) card[0][i] = A[i].first, card[1][i] = A[i].second;
  for (int i = 0; i < k; i++) oper[i] = B[i];
  for (int i = 0; i < n; i++, idx = 0) {
    for (int j = 0; j < k; j++) {
      idx ^= (card[idx][i] <= oper[j]);
    }
    ans += card[idx][i];
  }
  return ans;
}

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n, k, cnt = 0; cin >> n >> k; 
  ll ans = 0;
  map<int, int> cc;
  map<ll, ll> anti;
  vector<pii> A(n);
  for (auto &[x, y] : A) cin >> x >> y;
  vector<int> T(k);
  for (auto &e : T) cin >> e;
  if (k < 40000 && n < 40000) {
    cout << brute_force(n, k, A, T) << '\n';
    return 0;
  }
  for (auto [x, y] : A) cc[x], cc[y];
  for (auto e : T) cc[e];
  for (auto &[x, y] : cc) y = cnt++;
  for (auto &[x, y] : A) x = cc[x], y = cc[y];
  for (auto &e : T) e = cc[e];
  for (auto [x, y] : cc) anti[y] = x;

  segtree_max St_max;
  vector<query> Count(n);
  for (int i = 0; i < k; i++) {
    St_max.upd(T[i], i);
  }
  for (int i = 0; i < n; i++) {
    auto &[idx, sufix, val] = Count[i];
    idx = i;
    auto [l, r] = A[i];
    if (l > r) {
      sufix = St_max.query(r, l - 1);
      val = l;
    } else {
      sufix = St_max.query(l, r - 1);
      val = r;
    }
  }
  sort(all(Count));
  segtree_sum St_sum; vector<int> Ans(n);
  for (int i = k - 1; i >= 0; i--) {
    while (Count[cnt].sufix == i) {
      auto &[idx, sufix, val] = Count[cnt++];
      Ans[idx] = St_sum.query(val, Mxn - 1);
    }
    St_sum.upd(T[i], 1);
  }
  for (int i = 0; i < n; i++) {
    auto [l, r] = A[i];
    if (l > r) {
      swap(l, r);
      if (St_max.query(l, r - 1) == -1) {
        if (St_sum.query(r, Mxn - 1)%2 == 1) ans += anti[l];
        else ans += anti[r];
      } else {
        if (Ans[i]%2 == 1) ans += anti[l];
        else ans += anti[r];
      }
    } else {
      if (St_max.query(l, r - 1) == -1) {
        if (St_sum.query(r, Mxn - 1)%2 == 1) ans += anti[r];
        else ans += anti[l];
      } else {
        if (Ans[i]%2 == 1) ans += anti[l];
        else ans += anti[r];
      }
    }
  }
  cout << ans << '\n';
}

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