Submission #915963

#	Time	Username	Problem	Language	Result	Execution time	Memory
915963		rxlfd314	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	772 ms	173132 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
 
#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
 
#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)
 
constexpr int mxN = 200001, INF = 0x3f3f3f3f;
int N, K, SZ;
 
struct Node {
  int val;
  Node *lft, *rht;
  Node() : val(0), lft(nullptr), rht(nullptr) {}
  Node(int v) : val(v), lft(nullptr), rht(nullptr) {}
  Node(Node *v) : val(v->val), rht(v->rht), lft(v->lft) {}
  Node(Node *l, Node *r) {
    lft = l, rht = r;
    val = (l ? l->val : 0) + (r ? r->val : 0);
  }
};
 
Node *sts[mxN];
Node *build(int tl = 0, int tr = K) {
  if (tl == tr)
    return new Node();
  int tm = tl + tr >> 1;
  return new Node(build(tl, tm), build(tm+1, tr));
}
 
Node *upd(Node *n, int p, int v, int tl = 0, int tr = K) {
  if (tl == tr)
    return new Node(n->val + v);
  int tm = tl + tr >> 1;
  if (p <= tm)
    return new Node(upd(n->lft, p, v, tl, tm), n->rht);
  return new Node(n->lft, upd(n->rht, p, v, tm+1, tr));
}
 
int walk(Node *na, Node *nb, int tl = 0, int tr = K) {
  if (tl == tr)
    return tl;
  int tm = tl + tr >> 1;
  if (na->rht->val == nb->rht->val)
    return walk(na->lft, nb->lft, tl, tm);
  return walk(na->rht, nb->rht, tm+1, tr);
}
 
int qry(Node *n, int ql, int qr, int tl = 0, int tr = K) {
  if (tl > qr || tr < ql || qr < ql)
    return 0;
  if (ql <= tl && tr <= qr)
    return n->val;
  int tm = tl + tr >> 1;
  return qry(n->lft, ql, qr, tl, tm) + qry(n->rht, ql, qr, tm+1, tr);
}
 
signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  cin >> N >> K;
  int A[N], B[N];
  FOR(i, 0, N-1)
    cin >> A[i] >> B[i];
  
  int T[K];
  vt<int> cmp;
  FOR(i, 0, K-1)
    cin >> T[i], cmp.push_back(T[i]);
  
  sort(all(cmp));
  cmp.erase(unique(all(cmp)), end(cmp));
  cmp.push_back(INF);
  auto cind = [&](int i) {
    return lower_bound(all(cmp), i) - begin(cmp);
  };
  
  vt<int> inds[SZ=size(cmp)];
  FOR(i, 0, K-1)
    inds[cind(T[i])].push_back(i);
  vt<ari3> qrys[SZ];
  FOR(i, 0, N-1)
    qrys[cind(min(A[i], B[i]))].push_back({cind(max(A[i], B[i])), A[i], B[i]});
  
  ll ans = 0;
  sts[SZ-1] = new Node(build());
  ROF(i, SZ-1, 0) {
    if (i < SZ-1)    
      sts[i] = new Node(sts[i+1]);
    for (int j : inds[i])
      sts[i] = new Node(upd(sts[i], j, 1));
    for (auto [j, a, b] : qrys[i]) {
      if (i == j)
        ans += qry(sts[i], 0, K) & 1 ? b : a;
      else {
        int k = walk(sts[j], sts[i]);
        int v = qry(sts[j], k+1, K);
        ans += (a < b) ^ (v & 1) ? b : a;
      }
    }
  }
 
  cout << ans << '\n';
}

Compilation message (stderr)

fortune_telling2.cpp: In constructor 'Node::Node(Node*)':
fortune_telling2.cpp:20:15: warning: 'Node::rht' will be initialized after [-Wreorder]
   20 |   Node *lft, *rht;
      |               ^~~
fortune_telling2.cpp:20:9: warning:   'Node* Node::lft' [-Wreorder]
   20 |   Node *lft, *rht;
      |         ^~~
fortune_telling2.cpp:23:3: warning:   when initialized here [-Wreorder]
   23 |   Node(Node *v) : val(v->val), rht(v->rht), lft(v->lft) {}
      |   ^~~~
fortune_telling2.cpp: In function 'Node* build(int, int)':
fortune_telling2.cpp:34:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
fortune_telling2.cpp: In function 'Node* upd(Node*, int, int, int, int)':
fortune_telling2.cpp:41:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
fortune_telling2.cpp: In function 'int walk(Node*, Node*, int, int)':
fortune_telling2.cpp:50:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
fortune_telling2.cpp: In function 'int qry(Node*, int, int, int, int)':
fortune_telling2.cpp:61:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:92:48: warning: narrowing conversion of 'cind.main()::<lambda(int)>(((int)std::max<int>(A[i], B[i])))' from 'long int' to 'int' [-Wnarrowing]
   92 |     qrys[cind(min(A[i], B[i]))].push_back({cind(max(A[i], B[i])), A[i], B[i]});
      |                                            ~~~~^~~~~~~~~~~~~~~~~

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