// Problem: P5 - Dancing Elephants
// Contest: DMOJ - IOI '11
// URL: https://dmoj.ca/problem/ioi11p5
// Memory Limit: 256 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
using namespace std;
int n, l;
int x[150000], o[150000];
// int idx[150000];
void init(int N, int L, int X[])
{
n = N, l = L;
for(int i = 0; i < N; i++)
{
x[i] = X[i];
o[i] = x[i];
}
return;
}
int update(int i, int y)
{
int p = lower_bound(x, x+n, o[i])-x;
x[p] = y;
o[i] = y;
while(p && x[p] < x[p-1])
{
swap(x[p], x[p-1]);
p--;
}
while(p+1 < n && x[p] > x[p+1])
{
swap(x[p], x[p+1]);
p++;
}
int beg = x[0];
int ans = 1;
for(int j = 0; j < n; j++)
{
if(x[min(j+15, n-1)]-beg < l)
{
j = upper_bound(x+j, x+n, beg+l);
ans++;
continue;
}
if(x[j]-beg > l)
{
beg = x[j];
ans++;
}
}
return ans;
}
int main()
{
int m, o;
cin >> m >> o;
int gh[m];
for(int i = 0; i < m; i++) cin >> gh[i];
init(m, o, gh);
int q;
cin >> q;
while(q--)
{
int g, y;
cin >> g >> y;
cout << update(g, y) << '\n';
}
return 0;
}
Compilation message
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:51:19: error: invalid conversion from 'int*' to 'int' [-fpermissive]
51 | j = upper_bound(x+j, x+n, beg+l);
| ~~~~~~~~~~~^~~~~~~~~~~~~~~~~
| |
| int*
