#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
//#define int long long
//#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".ans","w",stdout)
#define pb push_back
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
#define getchar_unlocked getchar
inline int scan()
{
char c = getchar_unlocked();
int x = 0;
while(c<'0'||c>'9')
{
c=getchar_unlocked();
}
while(c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+c-'0';
c=getchar_unlocked();
}
return x;
}
void phongbeo();
const int inf=1e9+1;
const int mod2=1e9+9;
const int mod1=998244353;
struct icd
{
long double a;
int b;
};
struct ib
{
int a;
int b;
};
struct ic
{
int a,b,c;
};
struct id
{
int a,b,c,d;
};
struct ie
{
int a,b,c,d,e;
};
int n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,dem4,l,r,mid,l2,r2,center;
int i,s10,s12;
int kk;
int el=19;
int a[150001];
vector<int> v;
multiset<int> s;
set<int> snew;
int st[17][150002];
bool c[150001];
void calc()
{
v.clear();
s9=-1;
for(int i=1; i<=n; i++)
v.pb(a[i]), c[i]=0;
sort(v.begin(),v.end());
v.erase(unique(v.begin(), v.end()), v.end());
l=0;
for(int i=0; i<v.size(); i++)
{
while(l<v.size()&&v[i]+k>=v[l]) l++ ;
st[0][i+1]=l+1;
}
st[0][v.size()+1]=0;
s9=v.back();
mx=s9;
for(int i=1; i<17; i++)
for(int j=1; j<=v.size()+1; j++)
st[i][j]=st[i-1][st[i-1][j]];
snew.clear();
}
int S=365;
void init(int N, int L, int X[])
{
n=N;
k=L;
for(int i=1; i<=n; i++)
a[i]=X[i-1],s.insert(a[i]);
sort(a+1,a+1+n);
calc();
}
int update(int i, int y)
{
dem++;
l=i;
r=y;
l++;
auto it=s.lower_bound(a[l]);
if(!c[l])snew.insert(a[l]);
s.erase(it);
a[l]=r;
s.insert(r);
if(a[l]<=mx)
if(v[lower_bound(v.begin(),v.end(),a[l])-v.begin()]!=a[l])
{
snew.insert(a[l]),c[l]=1;
}
dem=snew.size();
if(snew.size()>=S)
calc();
s3=*s.rbegin();
s2=*s.begin();
s4=0 ;
while(s2<=s3)
{
s2=*s.lower_bound(s2);
if(s2+k>=s3)
{
s4++;
break;
}
s8=lower_bound(v.begin(),v.end(),s2)-v.begin()+1;
if(s2!=v[s8-1])
{
s4++;
s2+=k+1;
}
else
{
dem++;
if(snew.size()==0) s5=inf;
else if(s2>*snew.rbegin())s5=inf;
else s5=*snew.upper_bound(s2);
s6=s2-1;
s9=s8;
s12=0;
for(int i=16; i>=0; --i)
{
if(st[i][s8]==0) continue;
if(v[st[i][s8]-2]<=s5)
s6=v[st[i][s8]-2],s8=st[i][s8],s12=s12+(1<<i);
}
if(s12!=0)
{
s12--;
for(int i=16; i>=0; --i)
if(bit(s12,i))
s9=st[i][s9];
s2=v[s9-1];
}
s4+=s12;
if(s2>s3) break;
/// s2=*s.lower_bound(s2);
s4++;
s2+=k+1;
}
}
return s4;
}
Compilation message
elephants.cpp: In function 'void calc()':
elephants.cpp:84:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int i=0; i<v.size(); i++)
| ~^~~~~~~~~
elephants.cpp:86:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | while(l<v.size()&&v[i]+k>=v[l]) l++ ;
| ~^~~~~~~~~
elephants.cpp:93:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int j=1; j<=v.size()+1; j++)
| ~^~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:120:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
120 | if(a[l]<=mx)
| ^~
elephants.cpp:125:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
125 | dem=snew.size();
| ^~~
elephants.cpp:126:23: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
126 | if(snew.size()>=S)
| ~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
