제출 #1326356

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326356		apxo	커다란 상품 (IOI17_prize)	C++20	0 / 100	1068 ms	1114112 KiB

prize

#include "prize.h"
#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else 
#define debug(...)
#endif


mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
  assert(l <= r);
  return uniform_int_distribution<int> (l, r)(rng);
}
const int maxn = 2e5 + 5;
const int B = 478;
static int n;
vector<int> que[maxn];
int cnt_asks;
set<int> cnt_rank[maxn];
int id[maxn], cnt_id;
int rev[maxn];

struct fenwick_tree {
  int bit[maxn];
  
  void upd(int i, int v) {
    ++i;
    for (; i <= n; i += i & (-i)) bit[i] += v;
  }
  
  int get(int i) {
    ++i;
    int ans = 0;
    for (; i > 0; i -= i & (-i)) ans += bit[i];
    return ans;
  }
  
  int get(int l, int r) {
    return l > r ? 0 : get(r) - get(l - 1);
  }
} bit[6];

vector<int> abc(int i) {
  ++cnt_asks;
  if(que[i].empty()) {
    que[i] = ask(i);
    cnt_rank[que[i][0] + que[i][1]].insert(i);
    if (!id[que[i][0] + que[i][1]]) {
      id[que[i][0] + que[i][1]] = ++cnt_id;
      rev[cnt_id] = que[i][0] + que[i][1];
    }
    bit[id[que[i][0] + que[i][1]]].upd(i, 1);
  }
  return que[i];
}

int find_exp(int x, int l, int r) {
  int res = 0;
  for (int i = 1; i <= cnt_id; ++i) {
    if (rev[i] < x) {
      res += bit[i].get(l, r);
    }
  }
  return res;
}

int ans, mx;

void calc(int l, int r) {
  if (r - l < 2 || ans != -1) return;
  if (que[r][0] - que[l][0] == 0) return;
  int mid = l + (r - l) / 3 * 2;
  int pl = mid, pr = mid;
  bool skip_left = 0, skip_right = 0;
  while (pr < r) {
    abc(pr);
    int sum = que[pr][0] + que[pr][1];
    if (sum == 0) {
      ans = pr;
      return;
    }
    if ((int)cnt_rank[sum].size() > 1) {
      auto it = cnt_rank[sum].upper_bound(pr);
      if (it != cnt_rank[sum].end() and que[*it][0] - que[pr][0] == find_exp(sum, pr, *it)) {
        skip_right = 1;
        break;
      }
      it = cnt_rank[sum].lower_bound(pr);
      if (it != cnt_rank[sum].begin()) {
        --it;
        if (*it < l and que[pr][0] - que[*it][0] == find_exp(sum, *it, pr)) {
          skip_left = 1;
        }
      }
    }
    if (sum == mx) break;
    ++pr;
  }
  
  if (!skip_right) {
    calc(pr, r);
  }
  
  if (skip_left) return;
  
  while (pl > l) {
    abc(pl);
    int sum = que[pl][0] + que[pl][1];
    if (sum == 0) {
      ans = pl;
      return;
    }
    if ((int)cnt_rank[sum].size() > 1) {
      auto it = cnt_rank[sum].lower_bound(pl);
      if (it != cnt_rank[sum].begin()) {
        --it;
        if (que[pl][0] - que[*it][0] == find_exp(sum, *it, pl)) {
          skip_left = 1;
          break;
        }
      }
    }
    if (que[pl][0] + que[pl][1] == mx) break;
    --pl;
  }
  if (!skip_left) {
    calc(l, pl);
  }
}

int find_best(int N) {
  n = N;
  ans = -1;
  int x = min(n - 1, B);
  for (int i = 0; i <= x; ++i) {
    vector<int> cur = abc(i);
    if (cur[0] + cur[1] == 0) return i;
    mx = max(mx, cur[0] + cur[1]);
  }
  while (x >= 0) {
    if (que[x][0] + que[x][1] == mx) break;
    --x;
  }
  int lst = n - 1;
  while (lst >= 0) {
    vector<int> cur = abc(lst);
    if (cur[0] + cur[1] == 0) return lst;
    if (cur[0] + cur[1] == mx) break;
    --lst;
  }
  calc(x, lst);
  return ans;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 80