Submission #786597

#	Time	Username	Problem	Language	Result	Execution time	Memory
786597		Ahmed57	Dancing Elephants (IOI11_elephants)	C++17	50 / 100	9041 ms	3264 KiB

elephants

#include <bits/stdc++.h>

using namespace std;
int arr[50001],n,l;
unsigned short ind[50001],ind2[50001];
void init(int N,int L,int X[]){
    l = L;
    n = N;
    for(int i =0 ;i<n;i++){
        arr[i] = X[i];
        ind[i] = i;
        ind2[i] = i;
    }
}
int update(int i, int y){
    i = ind[i];
    arr[i] = y;
    if(arr[i]>arr[i-1]){
        while(i<n-1&&arr[i+1]<arr[i]){
            swap(arr[i],arr[i+1]);
            swap(ind[ind2[i]],ind[ind2[i+1]]);
            swap(ind2[i],ind2[i+1]);
            i++;
        }
    }else{
        while(i>0&&arr[i-1]>arr[i]){
            swap(arr[i],arr[i-1]);
            swap(ind[ind2[i]],ind[ind2[i-1]]);
            swap(ind2[i],ind2[i-1]);
            i--;
        }
    }
    int ans = 1 , la = arr[0];
    for(int i = 1;i<n;i++){
        if(arr[i]>la+l){
            la = arr[i];ans++;
        }
    }
    return ans;
}/*
int main(){
    int N = 4 , L = 10;
    int X[] ={10,15,17,20};
    init(N,L,X);
    cout<<update(2,16)<<endl;
    cout<<update(1,25)<<endl;
    cout<<update(3,35)<<endl;
    cout<<update(0,38)<<endl;
    cout<<update(2,0)<<endl;
}*/

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