oj.uz

Submission #788983

# Submission time Handle Problem Language Result Execution time Memory
788983 2023-07-20T19:06:48 Z Ronin13 Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 27128 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);
    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: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 8 ms 14420 KB Output is correct
2 Correct 6 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 6 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 6 ms 14420 KB Output is correct
7 Correct 1307 ms 15580 KB Output is correct
8 Correct 1314 ms 15836 KB Output is correct
9 Correct 1347 ms 16812 KB Output is correct
10 Correct 597 ms 16656 KB Output is correct
11 Correct 545 ms 16656 KB Output is correct
12 Correct 2368 ms 17192 KB Output is correct
13 Correct 557 ms 16684 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 6 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 6 ms 14420 KB Output is correct
7 Correct 1307 ms 15580 KB Output is correct
8 Correct 1314 ms 15836 KB Output is correct
9 Correct 1347 ms 16812 KB Output is correct
10 Correct 597 ms 16656 KB Output is correct
11 Correct 545 ms 16656 KB Output is correct
12 Correct 2368 ms 17192 KB Output is correct
13 Correct 557 ms 16684 KB Output is correct
14 Correct 1542 ms 16080 KB Output is correct
15 Correct 2009 ms 17728 KB Output is correct
16 Correct 3612 ms 19176 KB Output is correct
17 Correct 3761 ms 20332 KB Output is correct
18 Correct 3843 ms 20272 KB Output is correct
19 Correct 5481 ms 19988 KB Output is correct
20 Correct 3784 ms 20332 KB Output is correct
21 Correct 3522 ms 20332 KB Output is correct
22 Correct 882 ms 19308 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 6 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 6 ms 14420 KB Output is correct
7 Correct 1307 ms 15580 KB Output is correct
8 Correct 1314 ms 15836 KB Output is correct
9 Correct 1347 ms 16812 KB Output is correct
10 Correct 597 ms 16656 KB Output is correct
11 Correct 545 ms 16656 KB Output is correct
12 Correct 2368 ms 17192 KB Output is correct
13 Correct 557 ms 16684 KB Output is correct
14 Correct 1542 ms 16080 KB Output is correct
15 Correct 2009 ms 17728 KB Output is correct
16 Correct 3612 ms 19176 KB Output is correct
17 Correct 3761 ms 20332 KB Output is correct
18 Correct 3843 ms 20272 KB Output is correct
19 Correct 5481 ms 19988 KB Output is correct
20 Correct 3784 ms 20332 KB Output is correct
21 Correct 3522 ms 20332 KB Output is correct
22 Correct 882 ms 19308 KB Output is correct
23 Correct 8469 ms 27084 KB Output is correct
24 Correct 8811 ms 27128 KB Output is correct
25 Correct 4878 ms 26820 KB Output is correct
26 Correct 3864 ms 26392 KB Output is correct
27 Execution timed out 9050 ms 26360 KB Time limit exceeded
28 Halted 0 ms 0 KB -