oj.uz

답안 #728220

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
728220 2023-04-22T04:53:29 Z jampm 운세 보기 2 (JOI14_fortune_telling2) C++17
4 / 100
 1707 ms 20268 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 + 2;

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

//stress test brute force
ll brute_force(ll n, ll k, vector<pii> A, vector<int> B, ll ans = 0, ll idx = 0) {
  ll card[2][n], oper[k];
  for (int i = 0; i < n; i++) card[0][i] = A[i].first, card[1][i] = A[i].second;
  for (int i = 0; i < k; i++) oper[i] = B[i];
  for (int i = 0; i < n; i++, idx = 0) {
    for (int j = 0; j < k; j++) {
      idx ^= (card[idx][i] <= oper[j]);
    }
    ans += card[idx][i];
  }
  return ans;
}

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

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 5 ms 364 KB Output is correct
8 Correct 6 ms 340 KB Output is correct
9 Correct 5 ms 340 KB Output is correct
10 Correct 5 ms 340 KB Output is correct
11 Correct 5 ms 364 KB Output is correct
12 Correct 5 ms 340 KB Output is correct
13 Correct 5 ms 340 KB Output is correct

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 5 ms 364 KB Output is correct
8 Correct 6 ms 340 KB Output is correct
9 Correct 5 ms 340 KB Output is correct
10 Correct 5 ms 340 KB Output is correct
11 Correct 5 ms 364 KB Output is correct
12 Correct 5 ms 340 KB Output is correct
13 Correct 5 ms 340 KB Output is correct
14 Correct 424 ms 768 KB Output is correct
15 Correct 1707 ms 1236 KB Output is correct
16 Incorrect 99 ms 20268 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 5 ms 364 KB Output is correct
8 Correct 6 ms 340 KB Output is correct
9 Correct 5 ms 340 KB Output is correct
10 Correct 5 ms 340 KB Output is correct
11 Correct 5 ms 364 KB Output is correct
12 Correct 5 ms 340 KB Output is correct
13 Correct 5 ms 340 KB Output is correct
14 Correct 424 ms 768 KB Output is correct
15 Correct 1707 ms 1236 KB Output is correct
16 Incorrect 99 ms 20268 KB Output isn't correct
17 Halted 0 ms 0 KB -