oj.uz

Submission #1093957

# Submission time Handle Problem Language Result Execution time Memory
1093957 2024-09-28T06:52:38 Z Aviansh Dancing Elephants (IOI11_elephants) C++17
50 / 100
 9000 ms 5552 KB 
#include <bits/stdc++.h>
#include "elephants.h"

using namespace std;

int n;
int l;
int *x;
unordered_map<int,int>mp;
int uni[70000];
int siz = 0;

void init(int N, int L, int X[])
{
    n = N;
    l=L;
    x=X;
    for(int i = 0;i<n;i++){
        mp[x[i]]++;
    }
    for(pair<int,int>p:mp){
        uni[siz]=p.first;
        siz++;
    }
    sort(uni,uni+siz);
}

void rem(int ind){
    for(int i = ind+1;i<siz;i++){
        uni[i-1]=uni[i];
    }
    siz--;
}

void add(int ind , int val){
    siz++;
    for(int i = siz;i>ind;i--){
        uni[i]=uni[i-1];
    }
    uni[ind]=val;
}

int update(int i, int y)
{
    mp[x[i]]--;
    if(mp[x[i]]==0){
        mp.erase(x[i]);
        //uni.erase(lower_bound(uni.begin(),uni.end(),x[i]));
        for(int e = 0;e<siz;e++){
            if(uni[e]==x[i]){
                rem(e);
                break;
            }
        }
    }
    x[i]=y;
    mp[x[i]]++;
    if(mp[x[i]]==1){
        //int ind = lower_bound(uni.begin(),uni.end(),x[i])-uni.begin();
        //uni.insert(uni.begin()+ind,x[i]);
        if(uni[siz-1]<x[i]){
            add(siz,x[i]);
        }
        else{
            for(int e = 0;e<siz;e++){
                if(uni[e]>=x[i]){
                    add(e,x[i]);
                    break;
                }
            }
        }
    }
    int ans = 1;
    int las = uni[0];
    for(int i = 0;i<siz;i++){
        int curr = uni[i];
        if(curr-las>l){
            las=curr;
            ans++;
        }
    }
    return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1220 ms 2396 KB Output is correct
8 Correct 2389 ms 2908 KB Output is correct
9 Correct 3253 ms 5228 KB Output is correct
10 Correct 2344 ms 5216 KB Output is correct
11 Correct 2487 ms 4968 KB Output is correct
12 Correct 6664 ms 4968 KB Output is correct
13 Correct 2859 ms 4712 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1220 ms 2396 KB Output is correct
8 Correct 2389 ms 2908 KB Output is correct
9 Correct 3253 ms 5228 KB Output is correct
10 Correct 2344 ms 5216 KB Output is correct
11 Correct 2487 ms 4968 KB Output is correct
12 Correct 6664 ms 4968 KB Output is correct
13 Correct 2859 ms 4712 KB Output is correct
14 Correct 714 ms 3520 KB Output is correct
15 Correct 5013 ms 3948 KB Output is correct
16 Execution timed out 9063 ms 5552 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1220 ms 2396 KB Output is correct
8 Correct 2389 ms 2908 KB Output is correct
9 Correct 3253 ms 5228 KB Output is correct
10 Correct 2344 ms 5216 KB Output is correct
11 Correct 2487 ms 4968 KB Output is correct
12 Correct 6664 ms 4968 KB Output is correct
13 Correct 2859 ms 4712 KB Output is correct
14 Correct 714 ms 3520 KB Output is correct
15 Correct 5013 ms 3948 KB Output is correct
16 Execution timed out 9063 ms 5552 KB Time limit exceeded
17 Halted 0 ms 0 KB -