Submission #29166

#	Time	Username	Problem	Language	Result	Execution time	Memory
29166		PrOAhMeT	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	8696 ms	22812 KiB

elephants

#include <bits/stdc++.h>
#include "elephants.h"
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;

const int N=150005,SQ=395;	
int l,el[N],sq,dp[SQ][SQ*2+2],last[SQ][SQ*2+2],n,built;
vector<int> v[SQ];

void calc_bucket(int x) {
  int cur=v[x].size()-1;
  for(int i=v[x].size()-1;i>=0;--i) {
    while(cur>i&&v[x][cur]-v[x][i]>l)
      --cur;
    if(cur+1==v[x].size()) {
      dp[x][i]=1;
      last[x][i]=v[x][i]+l;
    }
    else {
      dp[x][i]=dp[x][cur+1]+1;
      last[x][i]=last[x][cur+1];
    }
  }
}

void rebuild() {
  //cout<<"Rebuilding..."<<endl;
  vector<int> k(n);
  for(int i=0;i<n;++i)
    k[i]=el[i];
  sort(k.begin(),k.end());
  int cur=0;
  v[0].clear();
  for(int i=0;i<n;++i) {
    if(i&&i%sq==0) {
      ++cur;
      v[cur].clear();
    }
    v[cur].pb(k[i]);
  }
  for(int i=0;i<=cur;++i)
    calc_bucket(i);
}

int find(int x) {
  int ret=0;
  while(1) {
    if(v[ret].size()==0) return ret-1;
    if(v[ret].back()>=x)
      return ret;
    ++ret;
  }
}

void Delete(int x,int y) {
  //cout<<"Deleting "<<x+1<<" "<<y<<endl;
  vector<int> tmp;
  int i=0;
  for(i=0;i<v[x].size()&&v[x][i]<y;++i)
    tmp.pb(v[x][i]);
  //cout<<"Till "<<i<<" "<<v[x][i]<<endl;
  ++i;
  for(;i<v[x].size();++i)
    tmp.pb(v[x][i]);
  swap(v[x],tmp);
  if(v[x].size()==0) {
    built=1;
    rebuild();
  }
  else calc_bucket(x);
}

void Insert(int x,int y) {
  //cout<<"Inserting "<<x+1<<" "<<y<<endl;
  vector<int> tmp;
  int i=0;
  for(i=0;i<v[x].size()&&v[x][i]<y;++i)
    tmp.pb(v[x][i]);
  tmp.pb(y);
  for(;i<v[x].size();++i)
    tmp.pb(v[x][i]);
  swap(v[x],tmp);
  if(v[x].size()>2*sq)
    rebuild();
  else calc_bucket(x);
}

int calculate() {
  int ret=0,cx=1,go,cy;
  ret=dp[0][0];
  go=last[0][0];
  while(1) {
    if(v[cx].size()==0)
      return ret;
    cy=upper_bound(v[cx].begin(),v[cx].end(),go)-v[cx].begin();
    if(cy==v[cx].size())
      ++cx;
    else {
      ret+=dp[cx][cy];
      go=last[cx][cy];
      ++cx;
    }
  }
}

void print() {
  cout<<"Printing:"<<endl;
  for(int i=0;v[i].size()!=0;++i) {
    for(int j=0;j<v[i].size();++j)
      cout<<v[i][j]<<" ";
    cout<<endl;
  }
  cout<<endl;
}

void printdp() {
  for(int i=0;v[i].size()!=0;++i) {
    for(int j=0;j<v[i].size();++j)
      cout<<dp[i][j]<<" "<<last[i][j]<<" ";
    cout<<endl;
  }
  cout<<endl;
}

void init(int nn,int k,int a[]) {
  sq=sqrt(nn);
  n=nn;
  l=k;
  for(int i=0;i<n;++i)
    el[i]=a[i];
  rebuild();
}

int update(int x,int y) {
  int t=el[x];
  el[x]=y;
  built=0;
  Delete(find(t),t);
  //print();
  if(!built)
    Insert(find(el[x]),el[x]);
  //print();
  //if(x==2&&y==0) printdp();
  return calculate();
}

//int main() {}

Compilation message (stderr)

elephants.cpp: In function 'void calc_bucket(int)':
elephants.cpp:21:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(cur+1==v[x].size()) {
             ^
elephants.cpp: In function 'void Delete(int, int)':
elephants.cpp:65:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0;i<v[x].size()&&v[x][i]<y;++i)
            ^
elephants.cpp:69:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(;i<v[x].size();++i)
         ^
elephants.cpp: In function 'void Insert(int, int)':
elephants.cpp:83:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0;i<v[x].size()&&v[x][i]<y;++i)
            ^
elephants.cpp:86:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(;i<v[x].size();++i)
         ^
elephants.cpp:89:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(v[x].size()>2*sq)
                 ^
elephants.cpp: In function 'int calculate()':
elephants.cpp:102:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(cy==v[cx].size())
          ^
elephants.cpp: In function 'void print()':
elephants.cpp:115:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<v[i].size();++j)
                  ^
elephants.cpp: In function 'void printdp()':
elephants.cpp:124:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<v[i].size();++j)
                  ^

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