oj.uz

답안 #551873

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
551873 2022-04-21T18:57:37 Z cadmiumsky 운세 보기 2 (JOI14_fortune_telling2) C++14
0 / 100
 11 ms 19156 KB 
#include <bits/stdc++.h>

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

int 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

fortune_telling2.cpp: In function 'void MTree::construct(int, int, int)':
fortune_telling2.cpp:19:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
fortune_telling2.cpp: In function 'int MTree::query(int, int, int, int, int)':
fortune_telling2.cpp:40:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
fortune_telling2.cpp: In function 'int MTree::descend(int, int, int, int, 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
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 19156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 19156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 19156 KB Output isn't correct
2 Halted 0 ms 0 KB -