oj.uz

답안 #728035

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
728035 2023-04-21T20:40:36 Z jampm 운세 보기 2 (JOI14_fortune_telling2) C++17
0 / 100
 8 ms 9940 KB 
#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 + 1;

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;}
};

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<int, int> anti;
  vector<pii> A(n);
  for (auto &[x, y] : A) cin >> x >> y;
  vector<int> T(k);
  for (auto &e : T) cin >> e;
  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));
  cnt = 0;
  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)&1) ans += anti[l];
        else ans += anti[r];
      } else {
        if (Ans[i]&1) ans += anti[l];
        else ans += anti[r];
      }
    } else {
      if (St_max.query(l, r - 1) == -1) {
        if (St_sum.query(r, Mxn - 1)&1) ans += anti[r];
        else ans += anti[l];
      } else {
        if (Ans[i]&1) ans += anti[l];
        else ans += anti[r];
      }
    }
  }
  cout << ans << '\n';
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 6 ms 9932 KB Output is correct
3 Incorrect 8 ms 9940 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 6 ms 9932 KB Output is correct
3 Incorrect 8 ms 9940 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 6 ms 9932 KB Output is correct
3 Incorrect 8 ms 9940 KB Output isn't correct
4 Halted 0 ms 0 KB -