oj.uz

Submission #915963

# Submission time Handle Problem Language Result Execution time Memory
915963 2024-01-25T03:19:49 Z rxlfd314 Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 772 ms 173132 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 2 ms 840 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 1 ms 1016 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 980 KB Output is correct
13 Correct 2 ms 860 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 2 ms 840 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 1 ms 1016 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 980 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 19 ms 7496 KB Output is correct
15 Correct 32 ms 15564 KB Output is correct
16 Correct 64 ms 23556 KB Output is correct
17 Correct 82 ms 31812 KB Output is correct
18 Correct 91 ms 31960 KB Output is correct
19 Correct 97 ms 31884 KB Output is correct
20 Correct 77 ms 31860 KB Output is correct
21 Correct 70 ms 31704 KB Output is correct
22 Correct 65 ms 30792 KB Output is correct
23 Correct 69 ms 30144 KB Output is correct
24 Correct 69 ms 29944 KB Output is correct
25 Correct 67 ms 30560 KB Output is correct
26 Correct 83 ms 31284 KB Output is correct
27 Correct 70 ms 31608 KB Output is correct
28 Correct 63 ms 31616 KB Output is correct
29 Correct 69 ms 31956 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 2 ms 840 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 1 ms 1016 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 980 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 19 ms 7496 KB Output is correct
15 Correct 32 ms 15564 KB Output is correct
16 Correct 64 ms 23556 KB Output is correct
17 Correct 82 ms 31812 KB Output is correct
18 Correct 91 ms 31960 KB Output is correct
19 Correct 97 ms 31884 KB Output is correct
20 Correct 77 ms 31860 KB Output is correct
21 Correct 70 ms 31704 KB Output is correct
22 Correct 65 ms 30792 KB Output is correct
23 Correct 69 ms 30144 KB Output is correct
24 Correct 69 ms 29944 KB Output is correct
25 Correct 67 ms 30560 KB Output is correct
26 Correct 83 ms 31284 KB Output is correct
27 Correct 70 ms 31608 KB Output is correct
28 Correct 63 ms 31616 KB Output is correct
29 Correct 69 ms 31956 KB Output is correct
30 Correct 480 ms 163604 KB Output is correct
31 Correct 522 ms 165840 KB Output is correct
32 Correct 603 ms 168212 KB Output is correct
33 Correct 772 ms 172896 KB Output is correct
34 Correct 447 ms 163104 KB Output is correct
35 Correct 732 ms 172860 KB Output is correct
36 Correct 732 ms 173060 KB Output is correct
37 Correct 752 ms 172688 KB Output is correct
38 Correct 674 ms 172752 KB Output is correct
39 Correct 649 ms 172744 KB Output is correct
40 Correct 540 ms 171824 KB Output is correct
41 Correct 644 ms 172992 KB Output is correct
42 Correct 622 ms 173132 KB Output is correct
43 Correct 512 ms 170696 KB Output is correct
44 Correct 465 ms 170580 KB Output is correct
45 Correct 482 ms 170752 KB Output is correct
46 Correct 553 ms 164708 KB Output is correct
47 Correct 479 ms 162492 KB Output is correct
48 Correct 522 ms 171608 KB Output is correct
49 Correct 495 ms 171204 KB Output is correct