Submission #780711

#	Time	Username	Problem	Language	Result	Execution time	Memory
780711		vjudge1	커다란 상품 (IOI17_prize)	C++17	94.48 / 100	53 ms	5148 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int K = 600;
const int nmax = 2e5 + 5;
int dimmax = 0;

int L[nmax * 2], R[nmax * 2];
int found = -1;
void fake(int x) {
  if(L[x] == -1) {auto v = ask(x - 1); L[x] = v[0]; R[x] = v[1]; }
  if(L[x] == 0 && R[x] == 0) found = x - 1;
}
int queryS(int x) { 
  fake(x);
  return L[x] + R[x];
}
int queryL(int x) { 
  fake(x);
  return L[x];
}
int queryR(int x) { 
  fake(x);
  return R[x];
}

#define lsb(x) (x & -x)
namespace AIB {
  int tree[2 * nmax];
  int len;
  void softinit(int nlen) { len = nlen; }
  void upd(int p, int x) {
    while(p <= len) tree[p] += x, p += lsb(p);
    return;
  }
  int conv(int p) {
    int sum = 0;
    while(p > 0) sum += tree[p], p -= lsb(p);
    return sum;
  }
  int deconv(int p) {
    p--;
    //cerr << "need to " << p << ' ';
    int lim = 0;
    for(int i = 18; i >= 0; i--) {
      if(lim + (1 << i) > len) continue;
      if(p >= tree[lim + (1 << i)])
        p -= tree[lim + (1 << i)], lim += (1 << i);
    }
    //cerr << lim + 1 << '\n';
    //if(lim == 5) {
      //cerr << "(\n";
      //for(int j = 1; j <= len; j++)
        //cerr << conv(j) - conv(j - 1) << ' ';
      //cerr << ")\n";
    //}
    return lim + 1;
  }
  
  void init() {
    for(int i = 1; i <= len; i++) upd(i, 1);
  }
}

#define mkcheck { if(found != -1) return found; }

using AIB::deconv;
using AIB::conv;
#define n ajsd
int n;


int getR(int x) {
  return (n - x) - (AIB::conv(n) - AIB::conv(x));
}

int find_best(int N) {
  n = N;
  AIB::softinit(N * 2);
  AIB::init();
  for(int i = 0; i < 2 * n; i++) L[i] = -1;
  bool fiter = 1;
  
  auto deactivate = [&](int x) {AIB::upd(x, -1); };
  
  for(int l = 1, r = min(n, 500); l <= n; l = r + 1, r = min(r + K, n)) {
    if(fiter) {
      fiter = 0;
      for(int j = l; j <= r; j++)
        dimmax = max(queryS(j), dimmax);
      for(int i = n + 1; i <= 2 * n; i++)
        L[i] = dimmax, R[i] = 0;
      for(int j = l; j <= r; j++) 
        if(queryS(j) != dimmax)
          deactivate(j);
    }
    else {
      int t = conv(r) + 1;
      while(queryS(deconv(t)) != dimmax) deactivate(t); mkcheck;
      t = deconv(t);
      int nl = AIB::conv(l - 1) + 1;
      while(deconv(nl) <= r && queryS(deconv(nl)) != dimmax) deactivate(deconv(nl)); mkcheck;
      if(deconv(nl) <= r) {
        for(int smth = 0; smth < queryR(deconv(nl)) - queryR(t); smth++) {
          
          int tmp = nl, base = deconv(nl);
          int ptrt = conv(t);
          bool ok = 0;
          for(int i = 9; i >= 0; i--) {
            if(nl + (1 << i) >= ptrt) continue;
            int u = deconv(nl + (1 << i)); 
            if(queryS(u) != dimmax) {  ok = 1; deactivate(u); mkcheck; break; }
            if(queryR(u) >= queryR(base) - smth) nl += (1 << i);
          }
          if(!ok) {
            nl++;
            deactivate(deconv(nl)); 
          }
          nl = tmp;
          mkcheck;
        }
      }
    }
    mkcheck;
  }
  mkcheck;
  assert(false);
  return -1;
  
}
#undef n
/**
      Anul asta se da centroid.
-- Surse oficiale
*/

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