# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1157317 | InvMOD | Dancing Elephants (IOI11_elephants) | C++17 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
using namespace std;
const int N = 2e5 + 5;
int n, len, a[N];
void init(int N, int L, int X[])
{
for(int i = 0; i < N; i++){
a[i + 1] = X[i];
}
n = N, len = L;
return;
}
int update(int ii, int y){
a[ii + 1] = y;
vector<int> pos(n + 1);
for(int i = 1; i <= n; i++)
pos[i] = a[i];
sort(1 + all(pos));
vector<int> dp(n + 1);
for(int i = 1, j = 1; i <= n; i++){
while(pos[i] - len > pos[j]) j++;
dp[i] = dp[j - 1] + 1;
}
return dp[n];
}
#define name "InvMOD"
#ifdef name
int32_t main(){
freopen(name".INP", "r", stdin);
freopen(name".OUT", "w", stdout);
int N, L; cin >> N >> L;
vector<int> X(N);
for(int i = 0; i < N; i++){
cin >> X[i];
}
init(N, L, X);
int q; cin >> q;
while(q--){
int i,y; cin >> i >> y;
cout << update(i, y) << "\n";
}
}
#endif // name
/* Test case
Input:
4 10
10 15 17 20
5
2 16
1 25
3 35
0 38
2 0
Output:
1
2
2
2
3
*/