oj.uz

Submission #122728

# Submission time Handle Problem Language Result Execution time Memory
122728 2019-06-29T07:42:48 Z nvmdava Dancing Elephants (IOI11_elephants) C++17
100 / 100
 7846 ms 11992 KB 
//#include "elephants.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pii pair<int, int>
using namespace std;
#define SQ 500
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) / SQ + 1);
   for(int i = 0; i < n; i++){
      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(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 % SQ == 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:68: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:93: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 400 ms 1528 KB Output is correct
8 Correct 406 ms 1780 KB Output is correct
9 Correct 522 ms 2784 KB Output is correct
10 Correct 602 ms 2756 KB Output is correct
11 Correct 580 ms 2632 KB Output is correct
12 Correct 1062 ms 2724 KB Output is correct
13 Correct 627 ms 2608 KB Output is correct

Subtask #4
47.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 400 ms 1528 KB Output is correct
8 Correct 406 ms 1780 KB Output is correct
9 Correct 522 ms 2784 KB Output is correct
10 Correct 602 ms 2756 KB Output is correct
11 Correct 580 ms 2632 KB Output is correct
12 Correct 1062 ms 2724 KB Output is correct
13 Correct 627 ms 2608 KB Output is correct
14 Correct 507 ms 2120 KB Output is correct
15 Correct 594 ms 2252 KB Output is correct
16 Correct 1685 ms 2920 KB Output is correct
17 Correct 1971 ms 3748 KB Output is correct
18 Correct 2036 ms 3668 KB Output is correct
19 Correct 1209 ms 3660 KB Output is correct
20 Correct 1903 ms 3836 KB Output is correct
21 Correct 1867 ms 3720 KB Output is correct
22 Correct 1143 ms 3668 KB Output is correct

Subtask #5
3.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 400 ms 1528 KB Output is correct
8 Correct 406 ms 1780 KB Output is correct
9 Correct 522 ms 2784 KB Output is correct
10 Correct 602 ms 2756 KB Output is correct
11 Correct 580 ms 2632 KB Output is correct
12 Correct 1062 ms 2724 KB Output is correct
13 Correct 627 ms 2608 KB Output is correct
14 Correct 507 ms 2120 KB Output is correct
15 Correct 594 ms 2252 KB Output is correct
16 Correct 1685 ms 2920 KB Output is correct
17 Correct 1971 ms 3748 KB Output is correct
18 Correct 2036 ms 3668 KB Output is correct
19 Correct 1209 ms 3660 KB Output is correct
20 Correct 1903 ms 3836 KB Output is correct
21 Correct 1867 ms 3720 KB Output is correct
22 Correct 1143 ms 3668 KB Output is correct
23 Correct 4244 ms 7200 KB Output is correct
24 Correct 4437 ms 7160 KB Output is correct
25 Correct 3639 ms 7192 KB Output is correct
26 Correct 4695 ms 7088 KB Output is correct
27 Correct 5447 ms 7124 KB Output is correct
28 Correct 1837 ms 2468 KB Output is correct
29 Correct 1778 ms 2460 KB Output is correct
30 Correct 1879 ms 2332 KB Output is correct
31 Correct 1766 ms 2428 KB Output is correct
32 Correct 4547 ms 7280 KB Output is correct
33 Correct 4333 ms 7148 KB Output is correct
34 Correct 4600 ms 7300 KB Output is correct
35 Correct 4539 ms 7184 KB Output is correct
36 Correct 133 ms 6904 KB Output is correct
37 Correct 7449 ms 7284 KB Output is correct
38 Correct 4745 ms 10868 KB Output is correct
39 Correct 4938 ms 11992 KB Output is correct
40 Correct 4978 ms 10940 KB Output is correct
41 Correct 7846 ms 11624 KB Output is correct
42 Correct 7832 ms 11804 KB Output is correct