Submission #916113

#	Time	Username	Problem	Language	Result	Execution time	Memory
916113		JakobZorz	Dancing Elephants (IOI11_elephants)	C++17	50 / 100	9030 ms	9176 KiB

elephants

#include"elephants.h"
#include<vector>
#include<algorithm>
using namespace std;

int n,l;
int pos[150000];
vector<int>arr;

void init(int N,int L,int X[]){
    n=N;
    l=L;
    for(int i=0;i<n;i++){
        pos[i]=X[i];
        arr.push_back(X[i]);
    }
    sort(arr.begin(),arr.end());
}

int update(int i,int y){
    auto it=lower_bound(arr.begin(),arr.end(),pos[i]);
    arr.erase(it);
    pos[i]=y;
    it=upper_bound(arr.begin(),arr.end(),pos[i]);
    arr.insert(it,y);
    
    int res=0;
    int pos=-1;
    for(int i=0;i<n;i++){
        if(arr[i]>pos){
            res++;
            pos=arr[i]+l;
        }
    }
    
    return res;
}

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