oj.uz

Submission #788964

# Submission time Handle Problem Language Result Execution time Memory
788964 2023-07-20T18:37:26 Z Ronin13 Dancing Elephants (IOI11_elephants) C++17
50 / 100
 2464 ms 18552 KB 
#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 pos, int ind){
    int cur = -1;
    int ans = 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 = lower_bound(vec.begin(), vec.end(), x) - vec.begin();
  //return ind;
//  cout << ind << ' ';
  rem(ind, x);
  
  a[i] = y;
  //return vec[0];
  ind = lower_bound(vec.begin(), vec.end(), y) - vec.begin();
  
  add(ind, y);
// return ind;
  int o =  go(0, 0);

  return o;
}

Compilation message

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(int, int)':
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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14416 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14416 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 7 ms 14432 KB Output is correct
6 Correct 6 ms 14424 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14416 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 7 ms 14432 KB Output is correct
6 Correct 6 ms 14424 KB Output is correct
7 Correct 1377 ms 16480 KB Output is correct
8 Correct 1346 ms 16836 KB Output is correct
9 Correct 1412 ms 18384 KB Output is correct
10 Correct 656 ms 18100 KB Output is correct
11 Correct 573 ms 18056 KB Output is correct
12 Correct 2464 ms 18552 KB Output is correct
13 Correct 571 ms 17784 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14416 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 7 ms 14432 KB Output is correct
6 Correct 6 ms 14424 KB Output is correct
7 Correct 1377 ms 16480 KB Output is correct
8 Correct 1346 ms 16836 KB Output is correct
9 Correct 1412 ms 18384 KB Output is correct
10 Correct 656 ms 18100 KB Output is correct
11 Correct 573 ms 18056 KB Output is correct
12 Correct 2464 ms 18552 KB Output is correct
13 Correct 571 ms 17784 KB Output is correct
14 Incorrect 752 ms 17648 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14416 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 7 ms 14432 KB Output is correct
6 Correct 6 ms 14424 KB Output is correct
7 Correct 1377 ms 16480 KB Output is correct
8 Correct 1346 ms 16836 KB Output is correct
9 Correct 1412 ms 18384 KB Output is correct
10 Correct 656 ms 18100 KB Output is correct
11 Correct 573 ms 18056 KB Output is correct
12 Correct 2464 ms 18552 KB Output is correct
13 Correct 571 ms 17784 KB Output is correct
14 Incorrect 752 ms 17648 KB Output isn't correct
15 Halted 0 ms 0 KB -