//#define TEST
#ifndef TEST
#include "elephants.h"
#endif // TEST
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef pair<int, int> ii;
const int len = 15e4+4;
int n, l, k, rem;
int hel[len], old[len];
struct bucket{
vector<int> vec;
vector<ii> nex;
void add(int v){
vec.insert(lower_bound(vec.begin(), vec.end(), v), v);
upd();
}
void del(int v){
vec.erase(lower_bound(vec.begin(), vec.end(), v));
upd();
}
void upd(){
nex.resize(vec.size());
for (int i = (int)vec.size()-1, j = vec.size(); i >= 0; i--){
while (vec[i]+l+1 <= vec[j-1])
j--;
if (j == vec.size())
nex[i] = mp(vec[i]+l+1, 1);
else
nex[i] = mp(nex[j].fi, nex[j].se+1);
}
}
void print(){
for (int i = 0; i < vec.size(); i++)
printf("%d ", vec[i]);
printf("\n");
for (int i = 0; i < nex.size(); i++)
printf("(%d, %d) ", nex[i].fi, nex[i].se);
printf("\n");
}
};
bucket data[len];
int fin(int v){
int l = 0, r = (n+k-1)/2-1, ans = -1;
if (data[r].vec.empty())
r--;
while (l <= r){
int mid = (l+r)/2;
if (data[mid].vec.back() >= v)
ans = mid, r = mid-1;
else
l = mid+1;
}
//printf("first bucket that contains element >= %d: %d\n", v, ans);
return ans;
}
int update(int pos, int val){
data[fin(old[pos])].del(old[pos]);
old[pos] = val;
int hey = fin(val);
if (hey == -1)
hey = (n+k-1)/k-1;
data[hey].add(val);
rem--;
//system("pause");
/*printf("rem = %d, buckets =\n", rem);
for (int i = 0; i*k < n; i++){
printf("bucket %d:\n", i);
data[i].print();
}*/
//system("pause");
if (rem == 0){
for (int i = 0, x = 0; i*k < n; i++){
for (int j = 0; j < data[i].vec.size(); j++)
hel[x++] = data[i].vec[j];
data[i].vec.clear();
}
for (int i = 0; i*k < n; i++){
for (int j = i*k; j < min(n, (i+1)*k); j++)
data[i].vec.pb(hel[j]);
data[i].upd();
}
rem = k-1;
}
/*printf("buckets after refresh\n");
for (int i = 0; i*k < n; i++){
printf("bucket %d:\n", i);
data[i].print();
}*/
int ans = 0, cur = 0;
while (true){
int b = fin(cur);
if (b == -1)
break;
int p = lower_bound(data[b].vec.begin(), data[b].vec.end(), cur)-data[b].vec.begin();
ans += data[b].nex[p].se;
cur = data[b].nex[p].fi;
}
return ans;
}
void init(int N, int L, int xs[]) {
n = N, l = L, k = 1606, rem = k-1; //1606;
for (int i = 0; i < n; i++)
old[i] = xs[i];
for (int i = 0; i*k < n; i++){
for (int j = i*k; j < min((i+1)*k, n); j++)
data[i].vec.pb(xs[j]);
data[i].upd();
}
/*for (int i = 0; i*k < n; i++){
printf("bucket %d:\n", i);
data[i].print();
}*/
}
#ifdef TEST
int main(){
int N, L, xs[len], M;
scanf("%d %d %d", &N, &L, &M);
for (int i = 0; i < N; i++)
scanf("%d", &xs[i]);
init(N, L, xs);
for (int i = 0; i < M; i++){
int a, b;
scanf("%d %d", &a, &b);
printf("%d\n", update(a, b));
}
return 0;
}
#endif
Compilation message
elephants.cpp: In member function 'void bucket::upd()':
elephants.cpp:40:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (j == vec.size())
~~^~~~~~~~~~~~~
elephants.cpp: In member function 'void bucket::print()':
elephants.cpp:48:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vec.size(); i++)
~~^~~~~~~~~~~~
elephants.cpp:52:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < nex.size(); i++)
~~^~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:98:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < data[i].vec.size(); j++)
~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
14840 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
14840 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
14840 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
14840 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
14840 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
