Submission #499082

#	Time	Username	Problem	Language	Result	Execution time	Memory
499082		600Mihnea	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	35 / 100	3057 ms	134696 KiB

fortune_telling2

#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;
  Node* lft;
  Node* rgh;
  Node(int l, int r) : l(l), r(r), mx(-INF), 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);
  } 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;
    if (node->lft) {
      node->mx = max(node->mx, node->lft->mx);
    }
    if (node->rgh) {
      node->mx = max(node->mx, node->rgh->mx);
    }
  }
}

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

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

 /// freopen ("input", "r", stdin);

  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;
    }
    int cnt = 0;
    for (int j = start; j <= q; j++) {
      cnt += (mx <= t[j]);
    }

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

  cout << sol << "\n";



  return 0;
}

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