oj.uz

답안 #788978

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
788978 2023-07-20T19:00:36 Z Ronin13 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
50 / 100
 2349 ms 17124 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) 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

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 6 ms 14420 KB Output is correct
3 Correct 6 ms 14420 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 6 ms 14420 KB Output is correct
3 Correct 6 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 6 ms 14420 KB Output is correct
6 Correct 6 ms 14420 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 6 ms 14420 KB Output is correct
3 Correct 6 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 6 ms 14420 KB Output is correct
6 Correct 6 ms 14420 KB Output is correct
7 Correct 1301 ms 15524 KB Output is correct
8 Correct 1296 ms 15836 KB Output is correct
9 Correct 1327 ms 16884 KB Output is correct
10 Correct 613 ms 16684 KB Output is correct
11 Correct 532 ms 16652 KB Output is correct
12 Correct 2349 ms 17124 KB Output is correct
13 Correct 555 ms 16664 KB Output is correct

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 6 ms 14420 KB Output is correct
3 Correct 6 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 6 ms 14420 KB Output is correct
6 Correct 6 ms 14420 KB Output is correct
7 Correct 1301 ms 15524 KB Output is correct
8 Correct 1296 ms 15836 KB Output is correct
9 Correct 1327 ms 16884 KB Output is correct
10 Correct 613 ms 16684 KB Output is correct
11 Correct 532 ms 16652 KB Output is correct
12 Correct 2349 ms 17124 KB Output is correct
13 Correct 555 ms 16664 KB Output is correct
14 Incorrect 734 ms 16080 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 6 ms 14420 KB Output is correct
3 Correct 6 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 6 ms 14420 KB Output is correct
6 Correct 6 ms 14420 KB Output is correct
7 Correct 1301 ms 15524 KB Output is correct
8 Correct 1296 ms 15836 KB Output is correct
9 Correct 1327 ms 16884 KB Output is correct
10 Correct 613 ms 16684 KB Output is correct
11 Correct 532 ms 16652 KB Output is correct
12 Correct 2349 ms 17124 KB Output is correct
13 Correct 555 ms 16664 KB Output is correct
14 Incorrect 734 ms 16080 KB Output isn't correct
15 Halted 0 ms 0 KB -