#include <bits/stdc++.h>
#define DIM 150010
#define DIMBUCKET 400
#include "elephants.h"
using namespace std;
int n,lg,nr_buckets,l,q,cnt,poz,val;
int what_bucket[DIM],x[DIM];
pair <int,int> v[DIM],aux[DIM],dp[DIMBUCKET][DIMBUCKET*2];
vector <pair<int,int> > buckets[DIMBUCKET];
void update_bucket (int bucket){
int el = 0;
for (auto it : buckets[bucket])
aux[++el] = it;
int j = el+1;
for (int i=el;i;i--){
while (aux[j-1].first > aux[i].first + l)
j--;
if (j <= el){
dp[bucket][i].first = dp[bucket][j].first + 1;
dp[bucket][i].second = dp[bucket][j].second;
} else {
dp[bucket][i].first = 1;
dp[bucket][i].second = aux[i].first + l;
}
}
}
void build (){
for (int i=1;i<=nr_buckets;i++)
buckets[i].clear();
sort (v+1,v+n+1);
for (int i=1;i<=n;i++){
what_bucket[v[i].second] = i / lg;
if (i % lg)
what_bucket[v[i].second]++;
buckets[what_bucket[v[i].second]].push_back(v[i]);
}
for (int i=1;i<=nr_buckets;i++)
sort (buckets[i].begin(),buckets[i].end());
/// dp[bucket][i] - nr min de intervale cu care pot sa acopar toate punctele
/// din bucketul asta, incepand de la al i - lea, si care e cea mai din dreapta poz
/// pt care pot sa fac asta
for (int i=1;i<=nr_buckets;i++){
update_bucket(i);
}
}
int query (){
int i = 1, val = -1, poz, sol = 0;
while (i <= nr_buckets){
if (buckets[i].empty()){
i++;
continue;
}
if (val == -1){
sol += dp[i][1].first;
val = dp[i][1].second;
i++;
} else {
if (buckets[i][ buckets[i].size()-1 ].first <= val)
i++;
else {
/// caut binar pe primul > val
int st = 1, dr = buckets[i].size(), sol_poz = 1;
while (st <= dr){
int mid = (st+dr)>>1;
if (buckets[i][mid-1].first > val){
sol_poz = mid;
dr = mid-1;
} else st = mid+1;
}
sol += dp[i][sol_poz].first;
val = dp[i][sol_poz].second;
i++;
}
}
}
return sol;
}
void init (int _n, int _l, int x[]){
n = _n, l = _l;
lg = n / sqrt (n); /// lungime bucket
nr_buckets = n / lg;
if (n % lg)
nr_buckets++;
for (int i=1;i<=n;i++){
v[i].first = x[i-1];
v[i].second = i;
}
build ();
}
void sterge (int idx, int poz){
int i;
for (i=0;i<buckets[idx].size();i++)
if (buckets[idx][i] == v[poz])
break;
for (int j=i+1;j<buckets[idx].size();j++)
buckets[idx][j-1] = buckets[idx][j];
buckets[idx].pop_back();
}
void adauga (int idx, int poz){
int i;
for (i=0;i<buckets[idx].size();i++)
if (v[poz].first <= buckets[idx][i].first)
break;
buckets[idx].push_back(make_pair(0,0));
for (int j=buckets[idx].size()-1;j>i;j--)
buckets[idx][j] = buckets[idx][j-1];
buckets[idx][i] = v[poz];
}
int update (int poz, int val){
cnt++;
if (cnt == lg){ /// refac bucketurile
build();
cnt = 0;
}
poz++;
int idx = what_bucket[poz];
sterge (idx,poz);
update_bucket (idx);
/// trb sa vad in ce bucket l as pune
v[poz].first = val;
int st = 1, dr = nr_buckets, sol = 1;
while (st <= dr){
int mid = (st+dr)>>1;
if (buckets[mid][0].first <= val){
sol = mid;
st = mid+1;
} else dr = mid-1;
}
what_bucket[poz] = sol;
adauga(sol,poz);
update_bucket(sol);
return query();
}
/*
int main (){
ifstream cin ("date.in");
ofstream cout ("date.out");
cin>>n>>l>>q;
for (int i=0;i<n;i++)
cin>>x[i];
init(n,l,x);
//cin>>q;
for (;q--;){
int useless;
cin>>poz>>val>>useless;
cout<<update (poz,val)<<"\n";
}
return 0;
}
*/
Compilation message
elephants.cpp: In function 'int query()':
elephants.cpp:69:26: warning: unused variable 'poz' [-Wunused-variable]
69 | int i = 1, val = -1, poz, sol = 0;
| ^~~
elephants.cpp: In function 'void sterge(int, int)':
elephants.cpp:138:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for (i=0;i<buckets[idx].size();i++)
| ~^~~~~~~~~~~~~~~~~~~~
elephants.cpp:142:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | for (int j=i+1;j<buckets[idx].size();j++)
| ~^~~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void adauga(int, int)':
elephants.cpp:150:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
150 | for (i=0;i<buckets[idx].size();i++)
| ~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
