oj.uz

Submission #29166

# Submission time Handle Problem Language Result Execution time Memory
29166 2017-07-18T13:25:16 Z PrOAhMeT Dancing Elephants (IOI11_elephants) C++14
100 / 100
 8696 ms 22812 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 20704 KB Output is correct
2 Correct 0 ms 20704 KB Output is correct
3 Correct 0 ms 20704 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 20704 KB Output is correct
2 Correct 0 ms 20704 KB Output is correct
3 Correct 0 ms 20704 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 20836 KB Output is correct
2 Correct 573 ms 21184 KB Output is correct
3 Correct 496 ms 21164 KB Output is correct
4 Correct 1116 ms 21208 KB Output is correct
5 Correct 1146 ms 21208 KB Output is correct
6 Correct 736 ms 21212 KB Output is correct
7 Correct 1083 ms 21208 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 816 ms 21092 KB Output is correct
2 Correct 606 ms 21004 KB Output is correct
3 Correct 979 ms 21164 KB Output is correct
4 Correct 1113 ms 21544 KB Output is correct
5 Correct 1206 ms 21600 KB Output is correct
6 Correct 7466 ms 21588 KB Output is correct
7 Correct 1129 ms 21536 KB Output is correct
8 Correct 1099 ms 21604 KB Output is correct
9 Correct 1703 ms 21588 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2943 ms 22084 KB Output is correct
2 Correct 2839 ms 22084 KB Output is correct
3 Correct 2469 ms 22084 KB Output is correct
4 Correct 5469 ms 22152 KB Output is correct
5 Correct 8696 ms 22152 KB Output is correct
6 Correct 726 ms 20704 KB Output is correct
7 Correct 623 ms 20704 KB Output is correct
8 Correct 706 ms 20704 KB Output is correct
9 Correct 636 ms 20704 KB Output is correct
10 Correct 6406 ms 22152 KB Output is correct
11 Correct 5913 ms 22152 KB Output is correct
12 Correct 5659 ms 22152 KB Output is correct
13 Correct 5296 ms 22812 KB Output is correct
14 Correct 2323 ms 22084 KB Output is correct
15 Correct 3006 ms 22160 KB Output is correct
16 Correct 5816 ms 22152 KB Output is correct
17 Correct 7923 ms 22152 KB Output is correct
18 Correct 6193 ms 22152 KB Output is correct
19 Correct 3663 ms 22160 KB Output is correct
20 Correct 3759 ms 22160 KB Output is correct