Submission #548576

#	Time	Username	Problem	Language	Result	Execution time	Memory
548576		Alex_tz307	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	319 ms	17984 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

const int kN = 2e5;
int aib[1 + kN];

void maxSelf(int &x, int y) {
  if (x < y) {
    x = y;
  }
}

struct ST {
  int n;
  vector<int> t;

  ST(int N) : n(N) {
    int dim = 1;
    while (dim < n) {
      dim *= 2;
    }
    t.resize(dim * 2);
  }

  void update(int x, int lx, int rx, int pos, int v) {
    if (lx == rx) {
      t[x] = v;
      return;
    }
    int mid = (lx + rx) / 2;
    if (pos <= mid) {
      update(x * 2, lx, mid, pos, v);
    } else {
      update(x * 2 + 1, mid + 1, rx, pos, v);
    }
    t[x] = max(t[x * 2], t[x * 2 + 1]);
  }

  void update(int pos, int v) {
    update(1, 1, n, pos, v);
  }

  int query(int x, int lx, int rx, int st, int dr) {
    if (st <= lx && rx <= dr) {
      return t[x];
    }
    int mid = (lx + rx) / 2, ans = 0;
    if (st <= mid) {
      maxSelf(ans, query(x * 2, lx, mid, st, dr));
    }
    if (mid < dr) {
      maxSelf(ans, query(x * 2 + 1, mid + 1, rx, st, dr));
    }
    return ans;
  }

  int query(int st, int dr) {
    if (dr < st) {
      return 0;
    }
    return query(1, 1, n, st, dr);
  }
};

void update(int x) {
  for (int i = x; i > 0; i = i & (i - 1)) {
    aib[i] += 1;
  }
}

int query(int x, int n) {
  int ans = 0;
  for (int i = x; i <= n; i += i & -i) {
    ans += aib[i];
  }
  return ans;
}

void testCase() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n + 1), b(n + 1);
  for (int i = 1; i <= n; ++i) {
    cin >> a[i] >> b[i];
  }
  vector<int> t(k + 1), v(k);
  for (int i = 1; i <= k; ++i) {
    cin >> t[i];
    v[i - 1] = t[i];
  }
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
  int N = v.size() + 1;
  ST st(N);
  for (int i = 1; i <= k; ++i) {
    t[i] = distance(v.begin(), upper_bound(v.begin(), v.end(), t[i]));
    st.update(t[i], i);
  }
  vector<vector<int>> cards(k + 1);
  for (int i = 1; i <= n; ++i) {
    int l = distance(v.begin(), lower_bound(v.begin(), v.end(), min(a[i], b[i]))) + 1;
    int r = distance(v.begin(), lower_bound(v.begin(), v.end(), max(a[i], b[i])));
    cards[st.query(l, r)].emplace_back(i);
  }
  int64_t ans = 0;
  for (int i = k; i >= 0; --i) {
    for (int index : cards[i]) {
      if (i != 0 && a[index] < b[index]) {
        swap(a[index], b[index]);
      }
      int pos = distance(v.begin(), lower_bound(v.begin(), v.end(), max(a[index], b[index]))) + 1;
      if (query(pos, N) % 2 == 1) {
        ans += b[index];
      } else {
        ans += a[index];
      }
    }
    update(t[i]);
  }
  cout << ans << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

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