Submission #860789

#	Time	Username	Problem	Language	Result	Execution time	Memory
860789		mgl_diamond	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	589 ms	51284 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;

#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()
#define file "input"

void setIO() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  if (fopen(file".inp", "r")) {
    freopen(file".inp", "r", stdin);
    freopen(file".out", "w", stdout);
  }
}

const int N = 2e5+5;
int n, k, a[N], b[N], t[N];
vector<int> sgt[N * 4];
ll ans;

void build(int id = 1, int lb = 1, int rb = k) {
  if (lb ^ rb) {
    int k = id << 1, mb = (lb + rb) >> 1;
    build(k, lb, mb);
    build(k+1, mb+1, rb);
    sgt[id].resize(sz(sgt[k]) + sz(sgt[k+1]));
    merge(all(sgt[k]), all(sgt[k+1]), sgt[id].begin());
  }
  else {
    sgt[id].push_back(t[lb]);
  }

  // cout << lb << " " << rb << ":\n";
  // fore(x, sgt[id]) cout << x << " ";
  // cout << "\n";
}

int query1(int v1, int v2, int r, int id = 1, int lb = 1, int rb = k) {
  if (lb > r) return -1;
  if (rb <= r) {
    // cout << lb << " " << rb << "\n";
    // cout << id << "\n";
    // fore(x, sgt[id]) cout << x << " ";
    // cout << "\n";
    auto it = lower_bound(all(sgt[id]), v1);
    if (it == sgt[id].end()) return -1;
    if (*it > v2) return -1;
  }
  if (lb == rb) {
    return lb;
  }
  int k = id << 1, mb = (lb + rb) >> 1;
  int ans = query1(v1, v2, r, k+1, mb+1, rb);
  if (ans == -1) ans = query1(v1, v2, r, k, lb, mb);
  return ans;
}

int query2(int l, int r, int value, int id = 1, int lb = 1, int rb = k) {
  if (l <= lb && rb <= r) {
    return sz(sgt[id]) - (lower_bound(all(sgt[id]), value) - sgt[id].begin());
  }
  else if (rb < l || lb > r) {
    return 0;
  }
  int k = id << 1, mb = (lb + rb) >> 1;
  return query2(l, r, value, k, lb, mb) + query2(l, r, value, k+1, mb+1, rb);
}

int main() {
  setIO();

  cin >> n >> k;
  foru(i, 1, n) cin >> a[i] >> b[i];
  foru(i, 1, k) cin >> t[i];
  int mx = *max_element(t+1, t+k+1);

  build();
  
  // cout << query1(9, 9, k) << "\n";

    // cout << query1(a[1], mx, k) << "\n";
  foru(i, 1, n) {
    if (a[i] == b[i]) {
      ans += a[i];
      continue;
    }

    // cout << a[i] << " " << b[i] << "\n";

    if (a[i] < b[i]) {
      int pos = query1(b[i], mx, k);

      if (pos < query1(a[i], mx, k)) {
        ans += b[i];
        continue;
      }

      int pos2 = max(0, query1(a[i], b[i]-1, pos-1));
      int cnt = query2(pos2+1, pos, b[i]);
      if ((cnt + (pos2 == 0)) & 1) ans += a[i];
      else ans += b[i];
    }
    else {
      int pos = query1(a[i], mx, k);

      if (pos < query1(b[i], mx, k)) {
        ans += a[i];
        continue;
      }

      int pos2 = max(0, query1(b[i], a[i]-1, pos-1));
      int cnt = query2(pos2+1, pos, a[i]);
      if (cnt & 1) ans += b[i];
      else ans += a[i];
    }

    // cout << ans << "\n";
  }

  cout << ans;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'void setIO()':
fortune_telling2.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     freopen(file".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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