Submission #1157320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157320		InvMOD	Dancing Elephants (IOI11_elephants)	C++17	26 / 100	9080 ms	1348 KiB

elephants

#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
*/

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3