JOI春合宿2012 Day4

Copy and Paste むずすぎ・・・
2完ゲーッ

Chinese

けっこう面倒。

#include <cstdio>
#include <deque>
#include <algorithm>

using namespace std;

struct seg_tree
{
  static const int DEPTH=18, SZ=1<<DEPTH;
  int data[SZ*2];
  seg_tree()
  {
    for(int i=0;i<SZ*2;i++) data[i] = 1000000000;
  }
  void init(int* d, int ln)
  {
    for(int i=0;i<ln;i++) data[i+SZ] = d[i];
    for(int i=ln;i<SZ;i++) data[i+SZ] = 1000000000;
    for(int i=SZ-1;i>=1;i--) data[i] = min(data[i*2], data[i*2+1]);
  }
  int query(int qL, int qR)
  {
    qL += SZ;
    qR += SZ;
    int ret = 1000000000;
    while(qL != qR){
      if(qL&1) ret = min(ret, data[qL++]);
      if(qR&1) ret = min(ret, data[--qR]);
      qL >>= 1; qR >>= 1;
    }
    return ret;
  }
};

int N, A[100000];
int ret[100000];

void solveA()
{
  deque<int> dq;
  for(int i=1;i<N;i++) dq.push_back((A[i] - i + N) % N);
  sort(dq.begin(), dq.end());

  for(int i=0;i<N;i++){
    //rotate
    while(dq.front() < i){
      dq.push_back(dq.front() + N);
      dq.pop_front();
    }

    int tmp = min(i, N-i);
    tmp += dq.back() - i;
    //ret[(N-i)%N] = min(ret[(N-i)%N], tmp);
    ret[i] = min(ret[i], tmp);
  }
}

void solveB()
{
  deque<int> dq;
  for(int i=1;i<N;i++) dq.push_back((N - (A[i] - i)) % N);
  sort(dq.begin(), dq.end());

  for(int i=0;i<N;i++){
    //rotate
    while(dq.front() < i){
      dq.push_back(dq.front() + N);
      dq.pop_front();
    }

    int tmp = min(i, N-i);
    tmp += dq.back() - i;
    ret[(N-i)%N] = min(ret[(N-i)%N], tmp);
    //ret[i] = min(ret[i], tmp);
  }
}

int val[200000];
int d1[200000], d2[200000];
seg_tree seg1, seg2;

void solveC()
{
  for(int i=1;i<N;i++) val[i-1] = ((A[i]-i)+N)%N;
  sort(val, val+(N-1));
  for(int i=0;i<N-1;i++) val[i+N-1] = val[i] + N;
  for(int i=0;i<2*N-3;i++){
    d1[i] = 2*val[i]-val[i+1];
    d2[i] = val[i]-2*val[i+1];
  }
  seg1.init(d1, 2*N-3);
  seg2.init(d2, 2*N-3);

  int left = 0;
  for(int i=0;i<N;i++){
    while(val[left]-i < 0) left++;

    int tmp = 1000000000;
    tmp = min(tmp, seg1.query(left, left+N-2) + (N) - i);
    tmp = min(tmp, seg2.query(left, left+N-2) + 2*(N) + i);
    //printf("%d %d\n", i, tmp);
    ret[i%N] = min(ret[i%N], tmp + min(i, N-i));
  }

}

int main()
{
  scanf("%d", &N);
  for(int i=1;i<N;i++){
    scanf("%d", A+i);
    --A[i];
  }

  for(int i=0;i<N;i++) ret[i] = 2100000000;
  solveA();
  solveB();
  solveC();

  for(int i=0;i<N;i++) printf("%d\n", ret[i]);

  return 0;
}

Copy and Paste

わからなかったから平方分割書いたらバグって絶望

Invitation

シミュレーションを Segment Tree を使って高速化した。

#include <cstdio>
#include <algorithm>

using namespace std;
const int MAX = 100000;
typedef long long i64;

struct range_tree
{
  struct node
  {
    node *back, *next;
    int id;
  };

  static const int DEPTH=19, SZ=1<<DEPTH;
  node pool[80 * MAX + 2*SZ]; int pLast;
  node* data[2*SZ];
  int ileft[MAX*2], iright[MAX*2];

  range_tree()
  {
    pLast = 0;
    for(int i=0;i<2*SZ;i++){
      data[i] = &(pool[pLast++]);
      data[i]->back = data[i]->next = NULL;
    }
    for(int i=0;i<MAX;i++) ileft[i] = iright[i] = -1;
  }

  void append(int pos, int id)
  {
    node* tmp = &(pool[pLast++]);
    tmp->back = data[pos];
    tmp->next = data[pos]->next;
    if(tmp->next) tmp->next->back = tmp;
    tmp->id = id;
    data[pos]->next = tmp;
  }

  void append(int L, int R, int id)
  {
    ileft[id] = pLast;
    L += SZ; R += SZ;
    while(L != R){
      if(L&1) append(L++, id);
      if(R&1) append(--R, id);
      L >>= 1; R >>= 1;
    }
    iright[id] = pLast;
  }

  void remove(node* N)
  {
    N->back->next = N->next;
    if(N->next) N->next->back = N->back;
  }

  void remove_all(int id)
  {
    for(int i=ileft[id]; i<iright[id]; i++)
      remove(&(pool[i]));
    ileft[id] = iright[id] = -1;
  }

  void each_remove(int pos, int* ret)
  {
    int rp = 0;
    pos += SZ;
    while(pos){
      for(node* nd=data[pos]->next; nd!=NULL; nd=nd->next){
	ret[rp++] = nd->id;
	remove_all(nd->id);
	remove_all(nd->id ^ 1); //complement
      }
      pos >>= 1;
    }
    ret[rp++] = -1;
  }
};

struct seg_tree
{
  static const int DEPTH=19, SZ=1<<DEPTH;
  int val[2*SZ], mx[2*SZ], azero[2*SZ];

  seg_tree()
  {
    for(int i=0;i<2*SZ;i++){
      val[i] = -1;
      mx[i] = 0;
      azero[i] = 0;
    }
  }

  void maximize(int pL, int pR, int qL, int qR, int v, int depth)
  {
    if((pR<<depth) <= qL || qR <= (pL<<depth)) return;
    if(qL <= (pL<<depth) && (pR<<depth) <= qR){
      val[pL] = max(val[pL], v);
      if((1<<depth) > azero[pL]) mx[pL] = max(val[pL], max(mx[pL*2], mx[pL*2+1]));
      else mx[pL] = -1;
      return;
    }

    maximize(pL*2, pL+pR, qL, qR, v, depth-1);
    maximize(pL+pR, pR*2, qL, qR, v, depth-1);
    mx[pL] = max(val[pL], max(mx[pL*2], mx[pL*2+1]));
  }

  void maximize(int qL, int qR, int v)
  {
    maximize(1, 2, qL+SZ, qR+SZ, v, DEPTH);
  }

  void zero_set(int p)
  {
    p += SZ;
    for(int i=0;p;i++){
      azero[p]++;
      if(val[p]!=-1){
	if((1<<i) <= azero[p]) mx[p] = -1;
	else mx[p] = max(max(mx[p*2], mx[p*2+1]), val[p]);
      }else{
	mx[p] = max(mx[p*2], mx[p*2+1]);
      }
      p >>= 1;
    }
  }

  pair<int, int> best_point()
  {
    int pos=1, mv=0, i=DEPTH;
    while(pos < SZ){
      if((1<<(i-1)) <= azero[pos*2]) pos = pos*2 + 1;
      else if((1<<(i-1)) <= azero[pos*2+1]) pos = pos*2;
      else if(max(mv, mx[pos*2]) < max(mv, mx[pos*2+1])){
	pos = pos*2 + 1;
      }else{
	pos = pos*2;
      }
      mv = max(mv, val[pos]);
      --i;
    }

    return make_pair(pos-SZ, mv);
  }

};

struct group
{
  int L1, R1, L2, R2, T;
  group(){ }
  group(int l1, int r1, int l2, int r2, int t)
  {
    L1 = l1; R1 = r1; L2 = l2; R2 = r2; T = t;
  }
};

int A, B, C, N;
int pos[4*MAX], pLast=0;
group G[MAX]; int weight[4*MAX];

range_tree range;
seg_tree seg;

int iTable[2*MAX+1];
void invite(int pos)
{
  range.each_remove(pos, iTable);
  for(int i=0;iTable[i]>=0;i++){
    int ps = iTable[i] / 2;
    seg.maximize(G[ps].L1, G[ps].R1, G[ps].T);
    seg.maximize(G[ps].L2, G[ps].R2, G[ps].T);
  }
}

int main()
{
  int p, q, r, s, t;
  scanf("%d%d%d%d", &A, &B, &C, &N);
  --C;
  for(int i=0;i<N;i++){
    scanf("%d%d%d%d%d", &p, &q, &r, &s, &t);
    --p; --r;
    r += A;  s += A;
    pos[pLast++] = p;
    pos[pLast++] = q;
    pos[pLast++] = r;
    pos[pLast++] = s;
    G[i] = group(p, q, r, s, t);
  }
  B += A;

  sort(pos, pos+pLast);
  pLast = unique(pos, pos+pLast) - pos;

  for(int i=0;i<pLast-1;i++){
    weight[i] = pos[i+1] - pos[i];
    if(pos[i]<=C && C<pos[i+1]){
      C = i;
      --weight[i];
    }
  }

  for(int i=0;i<N;i++){
    G[i].L1 = lower_bound(pos, pos+pLast, G[i].L1) - pos;
    G[i].L2 = lower_bound(pos, pos+pLast, G[i].L2) - pos;
    G[i].R1 = lower_bound(pos, pos+pLast, G[i].R1) - pos;
    G[i].R2 = lower_bound(pos, pos+pLast, G[i].R2) - pos;

    range.append(G[i].L1, G[i].R1, i*2);
    range.append(G[i].L2, G[i].R2, i*2+1);
  }

  invite(C);
  if(weight[C]==0) seg.zero_set(C);

  i64 ret = 0; int count = B - 1;

  pair<int, int> bLast = make_pair(-1, -1);

  while(count){
    pair<int, int> bp = seg.best_point();
    //printf("%d: %d\n", bp.first, bp.second);
    if(bp.second <= 0){
      puts("-1");
      return 0;
    }

    if(bLast == bp){
      //use all;
      ret += (i64)weight[bp.first] * bp.second;
      count -= weight[bp.first];
      weight[bp.first] = 0;
      seg.zero_set(bp.first);
      continue;
    }

    ret += bp.second;
    --count;
    invite(bp.first);
    if(--weight[bp.first]==0){
      seg.zero_set(bp.first);
    }
    bLast = bp;
  }
  printf("%lld\n", ret);

  return 0;
}