oj.uz

Submission #788985

# Submission time Handle Problem Language Result Execution time Memory
788985 2023-07-20T19:12:14 Z Ronin13 Dancing Elephants (IOI11_elephants) C++17
100 / 100
 7916 ms 28136 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 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);
    int xx = b[ind].size() - 1;
    while(xx > 0){
        if(b[ind][xx - 1] > b[ind][xx]) swap(b[ind][xx- 1], b[ind][xx]), xx--;
        else break;
    }
    //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 && b[ind].back() >= 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

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:103:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for(int i = 0; i < vvc.size(); i++){
      |                    ~~^~~~~~~~~~~~
elephants.cpp:102:9: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
  102 |     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 6 ms 14356 KB Output is correct
3 Correct 6 ms 14420 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 6 ms 14356 KB Output is correct
3 Correct 6 ms 14420 KB Output is correct
4 Correct 6 ms 14420 KB Output is correct
5 Correct 6 ms 14420 KB Output is correct
6 Correct 6 ms 14384 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 6 ms 14356 KB Output is correct
3 Correct 6 ms 14420 KB Output is correct
4 Correct 6 ms 14420 KB Output is correct
5 Correct 6 ms 14420 KB Output is correct
6 Correct 6 ms 14384 KB Output is correct
7 Correct 817 ms 15488 KB Output is correct
8 Correct 842 ms 15896 KB Output is correct
9 Correct 857 ms 16940 KB Output is correct
10 Correct 516 ms 16660 KB Output is correct
11 Correct 452 ms 16708 KB Output is correct
12 Correct 1677 ms 17236 KB Output is correct
13 Correct 490 ms 16668 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 6 ms 14356 KB Output is correct
3 Correct 6 ms 14420 KB Output is correct
4 Correct 6 ms 14420 KB Output is correct
5 Correct 6 ms 14420 KB Output is correct
6 Correct 6 ms 14384 KB Output is correct
7 Correct 817 ms 15488 KB Output is correct
8 Correct 842 ms 15896 KB Output is correct
9 Correct 857 ms 16940 KB Output is correct
10 Correct 516 ms 16660 KB Output is correct
11 Correct 452 ms 16708 KB Output is correct
12 Correct 1677 ms 17236 KB Output is correct
13 Correct 490 ms 16668 KB Output is correct
14 Correct 1002 ms 16188 KB Output is correct
15 Correct 1325 ms 16296 KB Output is correct
16 Correct 2713 ms 17336 KB Output is correct
17 Correct 2851 ms 18464 KB Output is correct
18 Correct 2783 ms 18564 KB Output is correct
19 Correct 2096 ms 17776 KB Output is correct
20 Correct 2826 ms 18400 KB Output is correct
21 Correct 2602 ms 18336 KB Output is correct
22 Correct 788 ms 17816 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 6 ms 14356 KB Output is correct
3 Correct 6 ms 14420 KB Output is correct
4 Correct 6 ms 14420 KB Output is correct
5 Correct 6 ms 14420 KB Output is correct
6 Correct 6 ms 14384 KB Output is correct
7 Correct 817 ms 15488 KB Output is correct
8 Correct 842 ms 15896 KB Output is correct
9 Correct 857 ms 16940 KB Output is correct
10 Correct 516 ms 16660 KB Output is correct
11 Correct 452 ms 16708 KB Output is correct
12 Correct 1677 ms 17236 KB Output is correct
13 Correct 490 ms 16668 KB Output is correct
14 Correct 1002 ms 16188 KB Output is correct
15 Correct 1325 ms 16296 KB Output is correct
16 Correct 2713 ms 17336 KB Output is correct
17 Correct 2851 ms 18464 KB Output is correct
18 Correct 2783 ms 18564 KB Output is correct
19 Correct 2096 ms 17776 KB Output is correct
20 Correct 2826 ms 18400 KB Output is correct
21 Correct 2602 ms 18336 KB Output is correct
22 Correct 788 ms 17816 KB Output is correct
23 Correct 6279 ms 22064 KB Output is correct
24 Correct 6713 ms 22092 KB Output is correct
25 Correct 3736 ms 21852 KB Output is correct
26 Correct 3619 ms 21472 KB Output is correct
27 Correct 6751 ms 21580 KB Output is correct
28 Correct 4421 ms 19428 KB Output is correct
29 Correct 4313 ms 19344 KB Output is correct
30 Correct 4426 ms 19440 KB Output is correct
31 Correct 4287 ms 19340 KB Output is correct
32 Correct 2318 ms 26008 KB Output is correct
33 Correct 2047 ms 25228 KB Output is correct
34 Correct 2561 ms 26036 KB Output is correct
35 Correct 2816 ms 28136 KB Output is correct
36 Correct 2158 ms 25956 KB Output is correct
37 Correct 7272 ms 27952 KB Output is correct
38 Correct 2643 ms 25136 KB Output is correct
39 Correct 5233 ms 26200 KB Output is correct
40 Correct 2459 ms 25052 KB Output is correct
41 Correct 7460 ms 27080 KB Output is correct
42 Correct 7916 ms 27236 KB Output is correct