Submission #1271261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271261		zNatsumi	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	384 ms	138136 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

#define int long long
const int N = 1e6 + 5;

int n, k, a[N], b[N], t[N];

int m, lst[N], lg[N], ot[N], oa[N];
int mx[N][25];
vector<int> rrh;

void init(){
  for(int i = 1; i <= n; i++){
    rrh.push_back(a[i]);
    rrh.push_back(b[i]);
  }
  for(int i = 1; i <= k; i++) rrh.push_back(t[i]);
  sort(rrh.begin(), rrh.end());
  rrh.erase(unique(rrh.begin(), rrh.end()), rrh.end());

  for(int i = 1; i <= n; i++){
    a[i] = lower_bound(rrh.begin(), rrh.end(), a[i]) - rrh.begin() + 1;
    b[i] = lower_bound(rrh.begin(), rrh.end(), b[i]) - rrh.begin() + 1;
  }
  for(int i = 1; i <= k; i++){
    t[i] = lower_bound(rrh.begin(), rrh.end(), t[i]) - rrh.begin() + 1;
    mx[t[i]][0] = max(mx[t[i]][0], i);
  }

  m = rrh.size();
  for(int j = 1; j <= 20; j++)
    for(int i = 1; i + (1 << j) - 1 <= m; i++)
      mx[i][j] = max(mx[i][j - 1], mx[i + (1 << j - 1)][j - 1]);

  for(int i = 2; i <= m; i++) lg[i] = lg[i/2] + 1;
}

int get(int l, int r){
  if(l > r) return 0;
  int k = lg[r - l + 1];
  return max(mx[l][k], mx[r - (1 << k) + 1][k]);
}

namespace bit{
  int bit[N];

  void update(int i, int y){
    for(; i <= k; i += i & -i) bit[i] += y;
  }
  int pref(int i){
    int res = 0;
    for(; i > 0; i -= i & -i) res += bit[i];
    return res;
  }
  int get(int l, int r){
    if(l > r) return 0;
    return pref(r) - pref(l - 1);
  }
};

void solve(){
  init();

  for(int i = 1; i <= n; i++){
    lst[i] = get(min(a[i], b[i]), max(a[i], b[i]) - 1);
    if(lst[i] && a[i] < b[i]) swap(a[i], b[i]);
    lst[i] += 1;
  }

  iota(ot + 1, ot + k + 1, 1);
  iota(oa + 1, oa + n + 1, 1);
  sort(ot + 1, ot + k + 1, [&](int i, int j){
          return t[i] > t[j];
       });
  sort(oa + 1, oa + n + 1, [&](int i, int j){
          return a[i] > a[j];
       });

  int res = 0;
  for(int i = 1, j = 0; i <= n; i++){
    while(j < k && t[ot[j + 1]] >= max(a[oa[i]], b[oa[i]])){
      j += 1;
      bit::update(ot[j], 1);
    }
    int cnt = bit::get(lst[oa[i]], k);
    if(cnt & 1) swap(a[oa[i]], b[oa[i]]);
    res += rrh[a[oa[i]] - 1];
  }
  cout << res << "\n";
}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> k;
  for(int i = 1; i <= n; i++) cin >> a[i] >> b[i];
  for(int i = 1; i <= k; i++) cin >> t[i];

  solve();

  return 0;
}

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