oj.uz

Submission #122735

# Submission time Handle Problem Language Result Execution time Memory
122735 2019-06-29T07:46:30 Z nvmdava Dancing Elephants (IOI11_elephants) C++17
100 / 100
 7471 ms 8356 KB 
//#include "elephants.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pii pair<int, int>
using namespace std;
#define SQ 600
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 380 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 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 404 ms 1524 KB Output is correct
8 Correct 452 ms 1876 KB Output is correct
9 Correct 540 ms 2948 KB Output is correct
10 Correct 536 ms 2876 KB Output is correct
11 Correct 557 ms 2892 KB Output is correct
12 Correct 1059 ms 2928 KB Output is correct
13 Correct 557 ms 3008 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 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 404 ms 1524 KB Output is correct
8 Correct 452 ms 1876 KB Output is correct
9 Correct 540 ms 2948 KB Output is correct
10 Correct 536 ms 2876 KB Output is correct
11 Correct 557 ms 2892 KB Output is correct
12 Correct 1059 ms 2928 KB Output is correct
13 Correct 557 ms 3008 KB Output is correct
14 Correct 536 ms 2128 KB Output is correct
15 Correct 644 ms 2348 KB Output is correct
16 Correct 1728 ms 3256 KB Output is correct
17 Correct 1974 ms 4224 KB Output is correct
18 Correct 2039 ms 4216 KB Output is correct
19 Correct 1383 ms 4332 KB Output is correct
20 Correct 2106 ms 4260 KB Output is correct
21 Correct 1875 ms 4260 KB Output is correct
22 Correct 1059 ms 4268 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 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 404 ms 1524 KB Output is correct
8 Correct 452 ms 1876 KB Output is correct
9 Correct 540 ms 2948 KB Output is correct
10 Correct 536 ms 2876 KB Output is correct
11 Correct 557 ms 2892 KB Output is correct
12 Correct 1059 ms 2928 KB Output is correct
13 Correct 557 ms 3008 KB Output is correct
14 Correct 536 ms 2128 KB Output is correct
15 Correct 644 ms 2348 KB Output is correct
16 Correct 1728 ms 3256 KB Output is correct
17 Correct 1974 ms 4224 KB Output is correct
18 Correct 2039 ms 4216 KB Output is correct
19 Correct 1383 ms 4332 KB Output is correct
20 Correct 2106 ms 4260 KB Output is correct
21 Correct 1875 ms 4260 KB Output is correct
22 Correct 1059 ms 4268 KB Output is correct
23 Correct 4045 ms 8180 KB Output is correct
24 Correct 4469 ms 8328 KB Output is correct
25 Correct 3483 ms 8180 KB Output is correct
26 Correct 4860 ms 8204 KB Output is correct
27 Correct 5146 ms 8216 KB Output is correct
28 Correct 2309 ms 2424 KB Output is correct
29 Correct 2191 ms 2336 KB Output is correct
30 Correct 2233 ms 2400 KB Output is correct
31 Correct 2154 ms 2368 KB Output is correct
32 Correct 4716 ms 8340 KB Output is correct
33 Correct 4168 ms 8320 KB Output is correct
34 Correct 4469 ms 8280 KB Output is correct
35 Correct 4029 ms 8252 KB Output is correct
36 Correct 123 ms 7804 KB Output is correct
37 Correct 6833 ms 8356 KB Output is correct
38 Correct 4404 ms 8276 KB Output is correct
39 Correct 4572 ms 8192 KB Output is correct
40 Correct 4426 ms 8200 KB Output is correct
41 Correct 7362 ms 8232 KB Output is correct
42 Correct 7471 ms 8072 KB Output is correct