oj.uz

Submission #122737

# Submission time Handle Problem Language Result Execution time Memory
122737 2019-06-29T07:48:52 Z nvmdava Dancing Elephants (IOI11_elephants) C++17
50 / 100
 805 ms 2980 KB 
//#include "elephants.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pii pair<int, int>
using namespace std;
#define SQ1 400
#define SQ2 800
int n, l;
int loc[150005];
int bid[150005];

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


inline 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;
   }
   return res;
}

inline 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;
inline void renew(int o){
   for(int i = 0; i < n; i++){
      sorted[i].ff = loc[i];
      sorted[i].ss = i;
   }
   if(!o){
      sort(sorted.begin(), sorted.end());
   }
   buck.clear();
   buck.resize((n - 1) / SQ1 + 1);
   for(int i = 0; i < n; i++){
      buck[i / SQ1].push_back({sorted[i].ff, {0, 0}});
      bid[sorted[i].ss] = i / SQ1;
   }
   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(1);
}
int cnt = 0;
inline 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);
}
inline 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 % SQ2 == 0){
      loc[j] = y;
      renew(0);
   } else {
      erase(buck[bid[j]], loc[j]);
      int t = upper_bound(buck.begin(), buck.end(), y, [](const int& lhs, const vector<pair<int, pii> >& rhs){
         return rhs.back().ff >= lhs;
      }) - buck.begin();
      if(t == buck.size()) t--;
      insert(buck[t], y);
      loc[j] = y;
      bid[j] = t;
   }
   return find();
}

Compilation message

elephants.cpp: In function 'void erase(std::vector<std::pair<int, std::pair<int, int> > >&, int&)':
elephants.cpp:69: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:94:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(t == buck.size()) t--;
          ~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 339 ms 1568 KB Output is correct
8 Correct 355 ms 1864 KB Output is correct
9 Correct 429 ms 2960 KB Output is correct
10 Correct 503 ms 2796 KB Output is correct
11 Correct 484 ms 2932 KB Output is correct
12 Correct 805 ms 2932 KB Output is correct
13 Correct 532 ms 2980 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 339 ms 1568 KB Output is correct
8 Correct 355 ms 1864 KB Output is correct
9 Correct 429 ms 2960 KB Output is correct
10 Correct 503 ms 2796 KB Output is correct
11 Correct 484 ms 2932 KB Output is correct
12 Correct 805 ms 2932 KB Output is correct
13 Correct 532 ms 2980 KB Output is correct
14 Incorrect 318 ms 2008 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 339 ms 1568 KB Output is correct
8 Correct 355 ms 1864 KB Output is correct
9 Correct 429 ms 2960 KB Output is correct
10 Correct 503 ms 2796 KB Output is correct
11 Correct 484 ms 2932 KB Output is correct
12 Correct 805 ms 2932 KB Output is correct
13 Correct 532 ms 2980 KB Output is correct
14 Incorrect 318 ms 2008 KB Output isn't correct
15 Halted 0 ms 0 KB -