#include "elephants.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
const int nx=150005, tx=390;
int n, c[nx], v[nx], l, cnt;
vector<int> vl[tx];
vector<pair<int, int>> dp[tx];
void calc(int x)
{
sort(vl[x].begin(), vl[x].end());
dp[x].resize(vl[x].size());
if (vl[x].size()==0) return;
for (int i=vl[x].size()-1; i>=0; i--)
{
if (upper_bound(vl[x].begin(), vl[x].end(), vl[x][i]+l)==vl[x].end())
{
dp[x][i].first=vl[x][i]+l;
dp[x][i].second=1;
}
else
{
int idx=upper_bound(vl[x].begin(), vl[x].end(), vl[x][i]+l)-vl[x].begin();
dp[x][i].first=dp[x][idx].first;
dp[x][i].second=dp[x][idx].second+1;
}
}
}
void build()
{
vector<pair<int, int>> d(n);
for (int i=0; i<n; i++) d[i].first=v[i], d[i].second=i;
sort(d.begin(), d.end());
for (int i=0; i<tx; i++) vl[i].clear();
for (int i=0; i<n; i++) c[d[i].second]=i/tx, vl[i/tx].push_back(d[i].first);
for (int i=0; i<tx; i++) calc(i);
}
int query()
{
int lst=-1, res=0;
for (int i=0; i<tx; i++)
{
if (vl[i].empty()||lst>=vl[i][vl[i].size()-1]) continue;
int idx=upper_bound(vl[i].begin(), vl[i].end(), lst)-vl[i].begin();
res+=dp[i][idx].second;
lst=dp[i][idx].first;
}
return res;
}
void init(int N, int L, int X[])
{
n=N; l=L;
for (int i=0; i<n; i++) v[i]=X[i];
build();
}
int update(int i, int y)
{
if ((++cnt)%tx==0)
{
v[i]=y;
build();
return query();
}
int loc=c[i];
vector<int> tmp;
bool f=0;
for (int i=0; i<vl[loc].size(); i++)
{
if (vl[loc][i]==v[i]&&!f)
{
f=1; continue;
}
else tmp.push_back(v[i]);
}
vl[loc]=tmp;
v[i]=y;
calc(loc);
for (int j=0; j<tx; j++)
{
if (j==tx-1)
{
vl[j].push_back(y);
c[i]=j;
calc(j);
}
else if (!vl[j].empty()&&vl[j][vl[j].size()-1]>=y)
{
vl[j].push_back(y);
c[i]=j;
calc(j);
break;
}
}
return query();
}
Compilation message
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:74:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for (int i=0; i<vl[loc].size(); i++)
| ~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
