Submission #788978

#	Time	Username	Problem	Language	Result	Execution time	Memory
788978		Ronin13	Dancing Elephants (IOI11_elephants)	C++17	50 / 100	2349 ms	17124 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>
#define ll long long 
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 200001;

int n;
int l;
int x;
vector <vector <int> > b(nmax);
vector <vector <int> > dp(nmax);
vector <vector <int> > nx(nmax);
int a[nmax];

vector <int> vec;

void rebuild_block(int ind){
  
   // sort(b[ind].begin(), b[ind].end());
  //  vec[ind] = b[ind].back();
    int n = b[ind].size();
    for(int i = n - 1; i >= 0; i--){
        int x = upper_bound(b[ind].begin(), b[ind].end(), b[ind][i] + l) - b[ind].begin();
        if(x == b[ind].size()){
            nx[ind][i] = i;
            dp[ind][i] = 1;
        }
        else{
            nx[ind][i] = nx[ind][x];
            dp[ind][i] = dp[ind][x] + 1;
        }
    }
}

int go(){
    int cur = -1;
    int ans = 0;
    int ind = 0;
    while(ind < vec.size()){
        if(b[ind].empty()) {
          ind++;
          continue;
        }
        if(b[ind].back() <= cur) {
          ind++;
          continue;
        }
        int x = upper_bound(b[ind].begin(), b[ind].end(), cur)  - b[ind].begin();
        ans += dp[ind][x];
        cur = b[ind][nx[ind][x]] + l;
        //cout << cur <<  ' ';
        ind++;
    }
  //  cout << "\n";
    return ans;
}

void rem(int ind, int x){
    for(int i = 0; i < b[ind].size(); i++){
        if(b[ind][i] == x){
            while(i < b[ind].size() - 1)
              swap(b[ind][i], b[ind][i + 1]), ++i;
            b[ind].pop_back();
            nx[ind].pop_back();
            dp[ind].pop_back();
            rebuild_block(ind);
            return;
        }
    }
}

void add(int ind, int x){
    b[ind].pb(x);
    nx[ind].pb(0);
    dp[ind].pb(0);
    sort(b[ind].begin(), b[ind].end());
    rebuild_block(ind);
}

int MX = 500;

void rebuild_all(){
    vector <int> vvc;
    for(int i = 0; i < 400; i++){
        for(int to : b[i])
          vvc.pb(to);
        b[i].clear(), dp[i].clear(), nx[i].clear();
    }
   
    int last;
    for(int i = 0; i < vvc.size(); i++){
        b[i / MX].pb(vvc[i]);
        last = i / MX;
    }
    for(int i = 0; i <= last; i++)
        dp[i].resize(b[i].size()), nx[i].resize(b[i].size());
    vec.resize(last + 1);
    //cout << dp[last].size();
    for(int j = last; j >= 0; j--){
      vec[j] = b[j].back();
     rebuild_block(j);
    }
    vec.pb(2e9);
}

void init(int N, int L, int X[])
{
  n = N;
  l = L;
  for(int i = 0; i < n; i++){
      b[0].pb(X[i]);
      a[i] = X[i];
  }
  sort(b[0].begin(), b[0].end());

  rebuild_all();
}

int c = 0;

int update(int i, int y){
  c++;
 if(c == MX){
      rebuild_all();
      c = 0;
  }
  
  int x = a[i];
  int ind = 0;
  //return 1;
  while(true){
      if(b[ind].empty()){
        ind++;
        continue;
      }
      if(vec[ind] >= x) break;
      ind++;
  }
 // return ind;
//  cout << ind << ' ';
  rem(ind, x);
  
  a[i] = y;
  //return vec[0];
  ind = 0;
  while(true){
      if(vec[ind] >= y) break;
      ind++;
  }
  add(ind, y);
// return ind;
  int o =  go();

  return o;
}

Compilation message (stderr)

elephants.cpp: In function 'void rebuild_block(int)':
elephants.cpp:31:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         if(x == b[ind].size()){
      |            ~~^~~~~~~~~~~~~~~~
elephants.cpp: In function 'int go()':
elephants.cpp:46:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     while(ind < vec.size()){
      |           ~~~~^~~~~~~~~~~~
elephants.cpp: In function 'void rem(int, int)':
elephants.cpp:66:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int i = 0; i < b[ind].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~
elephants.cpp:68:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             while(i < b[ind].size() - 1)
      |                   ~~^~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void rebuild_all()':
elephants.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for(int i = 0; i < vvc.size(); i++){
      |                    ~~^~~~~~~~~~~~
elephants.cpp:97:9: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
   97 |     int last;
      |         ^~~~

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