Submission #1197199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197199		julia_08	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	311 ms	16284 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MAXN = 2e5 + 10;
const int INF = 2e9;

struct node{
  int min, id;

  node(){
    min = INF;
  }
};

int a[MAXN], b[MAXN], t[MAXN], s[MAXN];

node seg[4 * MAXN];

int bit[3 * MAXN];

int n, k;

vector<int> all_c;

int ind(int x){
  return lower_bound(all_c.begin(), all_c.end(), x) - all_c.begin() + 1;
}

void update(int x, int lx, int rx, int i, int val){

  if(rx < i || lx > i) return;

  if(lx == rx){
    seg[x].min = val;
    seg[x].id = lx;
    return;
  }

  int m = (lx + rx) / 2, lc = 2 * x, rc = 2 * x + 1;

  update(lc, lx, m, i, val);
  update(rc, m + 1, rx, i, val);

  seg[x].min = min(seg[lc].min, seg[rc].min);
  seg[x].id = (seg[lc].min < seg[rc].min ? seg[lc].id : seg[rc].id);
}

pair<int, int> query(int x, int lx, int rx, int l, int r){

  if(rx < l || lx > r) return {INF, INF};

  if(l <= lx && rx <= r) return {seg[x].min, seg[x].id};

  int m = (lx + rx) / 2, lc = 2 * x, rc = 2 * x + 1;
  return min(query(lc, lx, m, l, r), query(rc, m + 1, rx, l, r));
}

void bit_add(int pos, int x){
  for(int i=pos; i<=(2 * n + k); i+=(i&-i)){
    bit[i] += x;
  }
}

int bit_query(int pos){
  int sum = 0;

  for(int i=pos; i>0; i-=(i&-i)){
    sum += bit[i];
  }

  return sum;
}

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

  cin >> n >> k;

  vector<pair<int, int>> ord;

  for(int i=1; i<=n; i++){

    cin >> a[i] >> b[i];

    if(a[i] > b[i]){
      s[i] = 1;
      swap(a[i], b[i]);
    }

    all_c.push_back(a[i]);
    all_c.push_back(b[i]);

    ord.push_back({b[i], i});

  }

  sort(ord.begin(), ord.end());

  for(int i=1; i<=k; i++){
    cin >> t[i];
    all_c.push_back(t[i]);
  }

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

  for(int i=0; i<n; i++) update(1, 1, n, i + 1, a[ord[i].second]);

  ll ans = 0;

  int tot = 0;

  for(int i=k; i>=1; i--){

    int pos = upper_bound(ord.begin(), ord.end(), make_pair(t[i], INF)) - ord.begin() + 1;

    if(pos > (int) ord.size()){
      bit_add(ind(t[i]), 1);
      tot ++;
      continue;
    }

    int j = query(1, 1, n, pos, n).second - 1;

    while(j < n && a[ord[j].second] <= t[i]){

      if((tot - bit_query(ind(a[ord[j].second]) - 1)) % 2 == 0){
        ans += b[ord[j].second];

      } else ans += a[ord[j].second];

      a[ord[j].second] = INF;

      update(1, 1, n, j + 1, INF);
      j = query(1, 1, n, pos, n).second - 1;

    }

    bit_add(ind(t[i]), 1);
    tot ++;

  }

  for(int i=0; i<n; i++){
    if(a[ord[i].second] != INF){

      if(s[ord[i].second]) swap(b[ord[i].second], a[ord[i].second]);

      if((tot - bit_query(ind(a[ord[i].second]) - 1)) % 2 == 0){
        ans += a[ord[i].second];

      } else ans += b[ord[i].second];

    }
  }

  cout << ans << "\n";

  return 0;
}

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