#include "elephants.h"
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=2e5+50;
const int mod=1e9+7;
const int sq=500;
using namespace std;
int n,l,x[nmax],nr,step;
vector<int>v[nmax],ad[nmax],nx[nmax];
multiset<int>s;
multiset<int>::iterator it;
void bld(int b)
{
int m=v[b].size();
int j=m;
nx[b].resize(m);
ad[b].resize(m);
for(int i=m-1;i>=0;i--)
{
while(v[b][i]+l<v[b][j-1])j--;
ad[b][i]=1;
nx[b][i]=v[b][i];
if(j<m)
{
ad[b][i]+=ad[b][j];
nx[b][i]=nx[b][j];
}
}
}
void build()
{
nr=(n+sq-1)/sq;
int j=0;
for(int i=0;i<nr;i++)v[i].clear(),nx[i].clear(),ad[i].clear();
for(it=s.begin();it!=s.end();it++)
{
v[j/sq].pb((*it));
j++;
}
for(int i=0;i<nr;i++)bld(i);
}
void init(int N,int L,int X[])
{
n=N,l=L;
for(int i=0;i<n;i++)
{
x[i]=X[i];
s.in(x[i]);
}
}
void del(int y)
{
for(int i=0;i<nr;i++)
{
if(!v[i].empty() && v[i][0]<=y && y<=v[i].back())
{
vector<int>nv;
for(int j=0;j<v[i].size();j++)
{
if(y!=v[i][j])nv.pb(v[i][j]);
else y=inf;
}
v[i]=nv;
bld(i);
break;
}
}
}
void add(int y)
{
for(int i=0;i<nr;i++)
{
if(!v[i].empty() && y<=v[i].back())
{
vector<int>nv;
for(int j=0;j<v[i].size();j++)
{
if(v[i][j]>y)nv.pb(y),y=inf;
nv.pb(v[i][j]);
}
if(y!=inf)nv.pb(y);
v[i]=nv;
bld(i);
break;
}
}
}
int update(int i,int y)
{
if(step%sq==0)build();
step++;
del(x[i]);
x[i]=y;
add(x[i]);
int pre=-inf;
int ans=0;
for(int i=0;i<nr;i++)
{
int lo=lower_bound(v[i].begin(),v[i].end(),pre)-v[i].begin();
if(lo!=v[i].size())
{
pre=nx[i][lo]+l+1;
ans+=ad[i][lo];
}
}
return ans;
}
/*int main()
{
//freopen("sol.in","r",stdin);
//freopen("sol.out","w",stdout);
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
return 0;
}*/
Compilation message
elephants.cpp: In function 'void del(int)':
elephants.cpp:70:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<v[i].size();j++)
~^~~~~~~~~~~~
elephants.cpp: In function 'void add(int)':
elephants.cpp:88:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<v[i].size();j++)
~^~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:112:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(lo!=v[i].size())
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
14464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
