oj.uz

답안 #122712

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122712 2019-06-29T07:19:32 Z nvmdava 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
0 / 100
 3 ms 632 KB 
#include "elephants.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pii pair<int, int>
using namespace std;
#define SQ 400
int n, l;
int loc[150005];
int bid[150005];

vector<vector<pair<int , pii> > > buck;
vector<pair<int, pii> > emp;
//{LOC {count, last} }


int find(){
   int res = 0;
   int lst = -1;
   for(auto& v : buck){
      if(v.empty() || v.back().ff <= lst) continue;
      int id = upper_bound(v.begin(), v.end(), lst, [](const int& lhs, const pair<int, pii>& rhs){
         return lhs < rhs.ff;
      }) - v.begin();
      res += v[id].ss.ff;
      lst = v[id].ss.ss;
      cerr<<lst<<' '<<res<<'\n';
   }
   return res;
}

void recalc(vector<pair<int, pii> >& vec){
   int sz = vec.size();
   int r = sz;
   for(int l = sz - 1; l >= 0; l--){
      while(vec[r - 1].ff > vec[l].ff + ::l) r--;
      vec[l].ss.ff = (r == sz ? 0 : vec[r].ss.ff) + 1;
      vec[l].ss.ss = (r == sz ? vec[l].ff + ::l : vec[r].ss.ss);
   }
}
vector<pii> sorted;
void renew(){
   for(int i = 0; i < n; i++){
      sorted[i].ff = loc[i];
      sorted[i].ss = i;
   }
   sort(sorted.begin(), sorted.end());
   buck.clear();
   for(int i = 0; i < n; i++){
      if(i % SQ == 0){
         buck.push_back(emp);
      }
      buck[i / SQ].push_back({sorted[i].ff, {0, 0}});
      bid[sorted[i].ss] = i / SQ;
   }
   for(auto& x : buck){
      recalc(x);
   }
}
void init(int N, int L, int X[]){
   n = N; l = L;
   for(int i = 0; i < n; i++){
      loc[i] = X[i];
   }
   sorted.resize(n);
   renew();
}
int cnt = 0;
void erase(vector<pair<int, pii> >& buck, int x){
   for(int i = 1; i < buck.size(); i++){
      if(buck[i - 1].ff == x) swap(buck[i - 1], buck[i]);
   }
   buck.pop_back();
   recalc(buck);
}
void insert(vector<pair<int, pii> >& buck, int x){
   buck.push_back({x, {0, 0}});
   int i = buck.size() - 1;
   while(i != 0 && buck[i - 1].ff > buck[i].ff){
      swap(buck[i - 1], buck[i]);
      i--;
   }
   recalc(buck);
}
int update(int j, int y){
   if(loc[j] == y) return find();
   if(++cnt % SQ == 0){
      loc[j] = y;
      renew();
   } else {
      erase(buck[bid[j]], loc[j]);
      for(int i = 0; i < buck.size(); i++){
         if(buck[i].back().ff >= y){
            insert(buck[i], y);
            loc[j] = y;
            bid[j] = i;
            break;
         }
      }
      if(loc[j] != y){
         insert(buck.back(), y);
         loc[j] = y;
         bid[j] = buck.size() - 1;
      }
   }
   return find();
}

Compilation message

elephants.cpp: In function 'void erase(std::vector<std::pair<int, std::pair<int, int> > >&, int)':
elephants.cpp:70:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 1; i < buck.size(); i++){
                   ~~^~~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:92:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < buck.size(); i++){
                      ~~^~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -