Submission #499085

#	Time	Username	Problem	Language	Result	Execution time	Memory
499085		600Mihnea	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	876 ms	257200 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;
  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 (stderr)

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 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65