Submission #551874

#	Time	Username	Problem	Language	Result	Execution time	Memory
551874		cadmiumsky	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	947 ms	75152 KiB

fortune_telling2

#include <bits/stdc++.h>
#define int long long
using namespace std;

// trei tipuri: None/ Set = 1/ Toggle

const int nmax = 2e5 + 5; 
vector<int> t;
int n, k;

namespace MTree {
  vector<int> aint[nmax * 4];
  vector<int> a, b;
  void construct(int node = 1, int cl = 0, int cr = k - 1) {
    if(cl == cr) {
      aint[node].push_back(t[cl]);
      return;
    }
    int mid = cl + cr >> 1;
    construct(2 * node, cl, mid);
    construct(2 * node + 1, mid + 1, cr);
    a = aint[node * 2];
    b = aint[node * 2 + 1];
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    while(!a.empty()) {
      if(a.back() > b.back())
        swap(a, b);
      aint[node].push_back(a.back());
      a.pop_back();
    }
    while(!b.empty())
      aint[node].push_back(b.back()), b.pop_back();
  }
  int query(int poz, int val, int node = 1, int cl = 0, int cr = k - 1) {
    if(cr < poz)
      return 0;
    if(poz <= cl)
      return distance(lower_bound(aint[node].begin(), aint[node].end(), val), aint[node].end()) & 1;
    int mid = cl + cr >> 1;
    return query(poz, val, 2 * node, cl, mid) ^ query(poz, val, 2 * node + 1, mid + 1, cr);
  }
  int descend(int l, int r, int node = 1, int cl = 0, int cr = k - 1) {
    if(lower_bound(aint[node].begin(), aint[node].end(), l) == upper_bound(aint[node].begin(), aint[node].end(), r))
      return cl - 1;
    if(cl == cr)
      return cl;
    int mid = cl + cr >> 1, temp = descend(l, r, 2 * node + 1, mid + 1, cr);
    if(temp == mid)
      return descend(l, r, 2 * node, cl, mid);
    return temp;
  }
};

int a[nmax], b[nmax];

signed main() {
  cin >> n >> k;
  for(int i = 0; i < n; i++)
    cin >> a[i] >> b[i];
  t.resize(k);
  for(auto &x : t)
    cin >> x;
  MTree::construct();
  int sum = 0;
  for(int i = 0; i < n; i++) {
    int start = a[i] > b[i];
    if(start)
      swap(a[i], b[i]);
    int u = MTree::descend(a[i], b[i] - 1);
    if(u != -1)
      start = 1;
    start ^= MTree::query(u + 1, b[i]);
    sum += (start ? b[i] : a[i]);
  }
  cout << sum << '\n';
  return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'void MTree::construct(long long int, long long int, long long int)':
fortune_telling2.cpp:19:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
fortune_telling2.cpp: In function 'long long int MTree::query(long long int, long long int, long long int, long long int, long long int)':
fortune_telling2.cpp:40:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
fortune_telling2.cpp: In function 'long long int MTree::descend(long long int, long long int, long long int, long long int, long long int)':
fortune_telling2.cpp:48:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |     int mid = cl + cr >> 1, temp = descend(l, r, 2 * node + 1, mid + 1, cr);
      |               ~~~^~~~

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