oj.uz

Submission #499085

# Submission time Handle Problem Language Result Execution time Memory
499085 2021-12-27T08:16:41 Z 600Mihnea Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 876 ms 257200 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;


const int N = 200000 + 7;
const int INF = (int) 1e9 + 7;
int n;
int q;
int a[N];
int b[N];
int t[N];

struct Node {
  int l;
  int r;
  int mx;
  int sum;
  Node* lft;
  Node* rgh;
  Node(int l, int r) : l(l), r(r), mx(-INF), sum(0), lft(nullptr), rgh(nullptr) {
  }
};

Node* root = new Node(1, (int) 1e9);

void upd(Node* node, int index) {
  assert(node->l <= t[index] && t[index] <= node->r);
  if (node->l == node->r) {
    node->mx = max(node->mx, index);
    node->sum++;
  } else {
    int mid = (node->l + node->r) / 2;
    if (t[index] <= mid) {
      if (!node->lft) {
        node->lft = new Node(node->l, mid);
      }
      upd(node->lft, index);
    } else {
      if (!node->rgh) {
        node->rgh = new Node(mid + 1, node->r);
      }
      upd(node->rgh, index);
    }
    node->mx = -INF;
    node->sum = 0;
    if (node->lft) {
      node->mx = max(node->mx, node->lft->mx);
      node->sum += node->lft->sum;
    }
    if (node->rgh) {
      node->mx = max(node->mx, node->rgh->mx);
      node->sum += node->rgh->sum;
    }
  }
}

int query(Node* node, int l, int r) {
  assert(!(node->r < l || r < node->l));
  if (l <= node->l && node->r <= r) {
    return node->mx;
  }
  int mid = (node->l + node->r) / 2, sol = -INF;

  if (node->lft && l <= mid) {
    sol = max(sol, query(node->lft, l, r));
  }
  if (node->rgh && mid + 1 <= r) {
    sol = max(sol, query(node->rgh, l, r));
  }
  return sol;
}

int querysum(Node* node, int l, int r) {
  assert(!(node->r < l || r < node->l));
  if (l <= node->l && node->r <= r) {
    return node->sum;
  }
  int mid = (node->l + node->r) / 2, sol = 0;

  if (node->lft && l <= mid) {
    sol += querysum(node->lft, l, r);
  }
  if (node->rgh && mid + 1 <= r) {
    sol += querysum(node->rgh, l, r);
  }
  return sol;
}
int the_current[N], the_start[N], ord[N];

bool cmp(int i, int j) {
  return the_start[i] > the_start[j];
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i] >> b[i];
  }

  for (int iq = 1; iq <= q; iq++) {
    cin >> t[iq];
    upd(root, iq);
  }

  ll sol = 0;
  for (int i = 1; i <= n; i++) {
    int mn = min(a[i], b[i]);
    int mx = max(a[i], b[i]);

    int start, current, v = query(root, mn, mx - 1);
    if (v == -INF) {
      start = 1;
      current = a[i];
    } else {
      start = v + 1;
      current = mx;
    }

    the_current[i] = current;
    the_start[i] = start;
    ord[i] = i;
  }

  root = new Node(1, (int) 1e9);

  int ff = q;

  sort(ord + 1, ord + n + 1, cmp);

  for (int iter = 1; iter <= n; iter++) {
    int i = ord[iter];
    int start = the_start[i];
    while (start <= ff) {
      upd(root, ff--);
    }
    int mn = min(a[i], b[i]);
    int mx = max(a[i], b[i]);

    int current = the_current[i];
    int cnt = querysum(root, mx, (int) 1e9);


    if (cnt % 2 == 0) {
      sol += current;
    } else {
      sol += a[i] + b[i] - current;
    }
  }

  cout << sol << "\n";



  return 0;
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:142:9: warning: unused variable 'mn' [-Wunused-variable]
  142 |     int mn = min(a[i], b[i]);
      |         ^~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1612 KB Output is correct
2 Correct 5 ms 2220 KB Output is correct
3 Correct 3 ms 1996 KB Output is correct
4 Correct 4 ms 2252 KB Output is correct
5 Correct 3 ms 2124 KB Output is correct
6 Correct 2 ms 1356 KB Output is correct
7 Correct 4 ms 2252 KB Output is correct
8 Correct 2 ms 1356 KB Output is correct
9 Correct 4 ms 1228 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 4 ms 2252 KB Output is correct
12 Correct 3 ms 2252 KB Output is correct
13 Correct 5 ms 2304 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1612 KB Output is correct
2 Correct 5 ms 2220 KB Output is correct
3 Correct 3 ms 1996 KB Output is correct
4 Correct 4 ms 2252 KB Output is correct
5 Correct 3 ms 2124 KB Output is correct
6 Correct 2 ms 1356 KB Output is correct
7 Correct 4 ms 2252 KB Output is correct
8 Correct 2 ms 1356 KB Output is correct
9 Correct 4 ms 1228 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 4 ms 2252 KB Output is correct
12 Correct 3 ms 2252 KB Output is correct
13 Correct 5 ms 2304 KB Output is correct
14 Correct 43 ms 17128 KB Output is correct
15 Correct 60 ms 28640 KB Output is correct
16 Correct 97 ms 46524 KB Output is correct
17 Correct 158 ms 56088 KB Output is correct
18 Correct 173 ms 60404 KB Output is correct
19 Correct 92 ms 30788 KB Output is correct
20 Correct 143 ms 60376 KB Output is correct
21 Correct 104 ms 30748 KB Output is correct
22 Correct 60 ms 5704 KB Output is correct
23 Correct 42 ms 4960 KB Output is correct
24 Correct 53 ms 4384 KB Output is correct
25 Correct 42 ms 6596 KB Output is correct
26 Correct 123 ms 59624 KB Output is correct
27 Correct 141 ms 60360 KB Output is correct
28 Correct 135 ms 51608 KB Output is correct
29 Correct 180 ms 60412 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1612 KB Output is correct
2 Correct 5 ms 2220 KB Output is correct
3 Correct 3 ms 1996 KB Output is correct
4 Correct 4 ms 2252 KB Output is correct
5 Correct 3 ms 2124 KB Output is correct
6 Correct 2 ms 1356 KB Output is correct
7 Correct 4 ms 2252 KB Output is correct
8 Correct 2 ms 1356 KB Output is correct
9 Correct 4 ms 1228 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 4 ms 2252 KB Output is correct
12 Correct 3 ms 2252 KB Output is correct
13 Correct 5 ms 2304 KB Output is correct
14 Correct 43 ms 17128 KB Output is correct
15 Correct 60 ms 28640 KB Output is correct
16 Correct 97 ms 46524 KB Output is correct
17 Correct 158 ms 56088 KB Output is correct
18 Correct 173 ms 60404 KB Output is correct
19 Correct 92 ms 30788 KB Output is correct
20 Correct 143 ms 60376 KB Output is correct
21 Correct 104 ms 30748 KB Output is correct
22 Correct 60 ms 5704 KB Output is correct
23 Correct 42 ms 4960 KB Output is correct
24 Correct 53 ms 4384 KB Output is correct
25 Correct 42 ms 6596 KB Output is correct
26 Correct 123 ms 59624 KB Output is correct
27 Correct 141 ms 60360 KB Output is correct
28 Correct 135 ms 51608 KB Output is correct
29 Correct 180 ms 60412 KB Output is correct
30 Correct 343 ms 135652 KB Output is correct
31 Correct 685 ms 254324 KB Output is correct
32 Correct 776 ms 254960 KB Output is correct
33 Correct 872 ms 249128 KB Output is correct
34 Correct 283 ms 127192 KB Output is correct
35 Correct 876 ms 257128 KB Output is correct
36 Correct 866 ms 257188 KB Output is correct
37 Correct 874 ms 257188 KB Output is correct
38 Correct 603 ms 131028 KB Output is correct
39 Correct 851 ms 257200 KB Output is correct
40 Correct 481 ms 131164 KB Output is correct
41 Correct 611 ms 131068 KB Output is correct
42 Correct 574 ms 131320 KB Output is correct
43 Correct 378 ms 128080 KB Output is correct
44 Correct 353 ms 121668 KB Output is correct
45 Correct 356 ms 109316 KB Output is correct
46 Correct 275 ms 23828 KB Output is correct
47 Correct 282 ms 23388 KB Output is correct
48 Correct 703 ms 254304 KB Output is correct
49 Correct 784 ms 252052 KB Output is correct