제출 #788502

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
788502		I_Love_EliskaM_	코끼리 (Dancing Elephants) (IOI11_elephants)	C++14	100 / 100	2853 ms	14780 KiB

elephants

#include "elephants.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0; i<n; ++i)
#define pb push_back
#define all(x) x.begin(),x.end()
#define pi pair<int,int>
#define f first
#define s second
mt19937 rng(998244353);

const int N=2e5+5;
int a[N];
int b[N];
 
const int K=400;
int block[K][2*K];
int nxt[K][2*K];
int val[K][2*K];
int sz[K];
pi go[K][2*K];

int n,len;


void make(int i) {
  int R=0;
  for (int L=0; L<sz[i]; ++L) {
    while (R<sz[i] && block[i][R]-block[i][L]<=len) ++R;
    nxt[i][L]=R;
    val[i][L]=block[i][L]+len;
  }

  for (int j=sz[i]-1; j>=0; --j) {
    if (nxt[i][j]==sz[i]) {
      go[i][j]={1,val[i][j]};
    } else {
      go[i][j]={go[i][nxt[i][j]].f+1,go[i][nxt[i][j]].s};
    }
  }
}

void build() {
  n=0;
  forn(i,K) {
    forn(j,sz[i]) b[n++]=block[i][j];
  }
  for(int l=0; l<n; l+=K) {
    int r=min(l+K,n);
    sz[l/K]=r-l;
    for(int i=l; i<r; ++i) {
      block[l/K][i-l]=b[i];
    }

    int i=l/K;
    make(i); 
  }
}

void init(int _n, int _l, int x[]) {
  n=_n; len=_l;
  forn(i,n) a[i]=x[i];
  forn(i,n) b[i]=a[i];
  sort(b,b+n);

  for(int l=0; l<n; l+=K) {
    int r=min(l+K,n);
    sz[l/K]=r-l;
    for(int i=l; i<r; ++i) {
      block[l/K][i-l]=b[i];
    }
  }

  build();

}

void rem(int i, int x) {
  forn(j,sz[i]) {
    if (block[i][j]<x) continue;
    block[i][j]=block[i][j+1];
  }
  --sz[i];
  make(i);
}
void del(int x) {
  for (int i=0; i<K; ++i) {
    if (x<=block[i][sz[i]-1]) {
      rem(i,x);
      break;
    }
  }
}

void insert(int i, int x) {
  int z=1;
  int t=x;
  forn(j,sz[i]) {
    if (block[i][j]<x) continue;
    swap(t,block[i][j]);
  }
  block[i][sz[i]]=t;
  ++sz[i];
  make(i);
}
void add(int x) {
  for (int i=0; i<K; ++i) {
    if (x<=block[i][sz[i]-1]) {
      insert(i,x);
      break;
    }
    if (i==(n-1)/K) {
      insert(i,x);
      break;
    }
  }
}

int Q=0;
int update(int ind, int x) {
  
  del(a[ind]);
  a[ind]=x;
  add(a[ind]);

  ++Q;
  if (Q==K) {
    Q=0;
    build();
  }

  //forn(i,n) {
  //  if (!sz[i]) break;
  //  forn(j,sz[i]) cout<<block[i][j]<<' '; cout<<'\n';
  //  forn(j,sz[i]) cout<<nxt[i][j]<<' '; cout<<'\n';
  //  forn(j,sz[i]) cout<<val[i][j]<<' '; cout<<'\n';
  //  forn(j,sz[i]) cout<<go[i][j].f<<','<<go[i][j].s<<"  "; cout<<'\n';
  //}

  int i=0, j=0, pos=block[0][0];
  int ans=0;

  for (;sz[i];) {
    auto it = go[i][j];
    ans += it.f;
    pos = it.s;

    while (sz[i] && block[i][sz[i]-1]<=pos) ++i;
    if (!sz[i]) break;
    int l=0, r=sz[i]-1;
    while (l<r) {
      int m=(l+r)>>1;
      if (block[i][m]<=pos) l=m+1;
      else r=m;
    }
    j=r;
  }
  return ans;

}

컴파일 시 표준 에러 (stderr) 메시지

elephants.cpp: In function 'void insert(int, int)':
elephants.cpp:98:7: warning: unused variable 'z' [-Wunused-variable]
   98 |   int z=1;
      |       ^

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3