oj.uz

Submission #122724

# Submission time Handle Problem Language Result Execution time Memory
122724 2019-06-29T07:40:10 Z nvmdava Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 7784 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;
//{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 344 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 344 KB Output is correct
7 Correct 326 ms 1464 KB Output is correct
8 Correct 366 ms 1760 KB Output is correct
9 Correct 557 ms 2876 KB Output is correct
10 Correct 692 ms 2720 KB Output is correct
11 Correct 666 ms 2912 KB Output is correct
12 Correct 1145 ms 2984 KB Output is correct
13 Correct 736 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 376 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 326 ms 1464 KB Output is correct
8 Correct 366 ms 1760 KB Output is correct
9 Correct 557 ms 2876 KB Output is correct
10 Correct 692 ms 2720 KB Output is correct
11 Correct 666 ms 2912 KB Output is correct
12 Correct 1145 ms 2984 KB Output is correct
13 Correct 736 ms 3008 KB Output is correct
14 Correct 508 ms 2020 KB Output is correct
15 Correct 575 ms 2336 KB Output is correct
16 Correct 1780 ms 3264 KB Output is correct
17 Correct 2164 ms 4000 KB Output is correct
18 Correct 2263 ms 4108 KB Output is correct
19 Correct 1392 ms 3924 KB Output is correct
20 Correct 2097 ms 4016 KB Output is correct
21 Correct 2108 ms 3840 KB Output is correct
22 Correct 1346 ms 3820 KB Output is correct

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 344 KB Output is correct
7 Correct 326 ms 1464 KB Output is correct
8 Correct 366 ms 1760 KB Output is correct
9 Correct 557 ms 2876 KB Output is correct
10 Correct 692 ms 2720 KB Output is correct
11 Correct 666 ms 2912 KB Output is correct
12 Correct 1145 ms 2984 KB Output is correct
13 Correct 736 ms 3008 KB Output is correct
14 Correct 508 ms 2020 KB Output is correct
15 Correct 575 ms 2336 KB Output is correct
16 Correct 1780 ms 3264 KB Output is correct
17 Correct 2164 ms 4000 KB Output is correct
18 Correct 2263 ms 4108 KB Output is correct
19 Correct 1392 ms 3924 KB Output is correct
20 Correct 2097 ms 4016 KB Output is correct
21 Correct 2108 ms 3840 KB Output is correct
22 Correct 1346 ms 3820 KB Output is correct
23 Correct 4916 ms 7512 KB Output is correct
24 Correct 5442 ms 7588 KB Output is correct
25 Correct 4233 ms 7528 KB Output is correct
26 Correct 5843 ms 7784 KB Output is correct
27 Correct 6497 ms 7780 KB Output is correct
28 Correct 1550 ms 2320 KB Output is correct
29 Correct 1469 ms 2424 KB Output is correct
30 Correct 1551 ms 2424 KB Output is correct
31 Correct 1473 ms 2428 KB Output is correct
32 Correct 5613 ms 7756 KB Output is correct
33 Correct 5589 ms 7784 KB Output is correct
34 Correct 5825 ms 7584 KB Output is correct
35 Correct 5440 ms 7556 KB Output is correct
36 Correct 155 ms 7288 KB Output is correct
37 Execution timed out 9006 ms 7528 KB Time limit exceeded
38 Halted 0 ms 0 KB -