oj.uz

Submission #269748

# Submission time Handle Problem Language Result Execution time Memory
269748 2020-08-17T09:35:08 Z teee Dancing Elephants (IOI11_elephants) C++14
26 / 100
 20 ms 2176 KB 
#include <iostream>
#include <algorithm>
#include "elephants.h"
using namespace std;
const int sz=388;
int l,mg,upcnt;
struct bucket{
    int val[sz<<1],cnt[sz<<1],last[sz<<1],size;
    void upd(){
        int t=size-1;
        for(int i=size-1;i>=0;i--){
            while(t!=i&&val[t-1]-val[i]>l)t--;
            if(val[size-1]-val[i]<=l) cnt[i]=1,last[i]=val[i]+l;
            else cnt[i]=cnt[t]+1,last[i]=last[t];
        }
    }
} buck[sz];
int arr[150'010], temp[150'010];
void refresh(){
    int cnt=0;
    for(int i=0;i<=mg;i++){
        for(int j=0;j<buck[i].size;j++){
            temp[cnt++]=buck[i].val[j];
        }buck[i].size=0;
    }
    int t=sz,tg=0;
    for(int i=0;i<cnt;i++){
        if(i==t) t+=sz,tg++;
        buck[tg].val[i-t+sz]=temp[i];
        buck[tg].size++;
    }
    for(int i=0;i<=mg;i++){
        buck[i].upd();
    }
    upcnt=0;
}
int remove(int val){
    int t=0;
    for(;t<=mg;t++)if(buck[t].val[buck[t].size-1]>=val&&buck[t].val[0]<=val)break;
    for(int i=buck[t].size-1;i>=0;i--){
        if(buck[t].val[i]==val){
            for(int j=i+1;j<buck[t].size;j++){
                buck[t].val[j-1]=buck[t].val[j];
            }
            break;
        }
    }
    buck[t].size--;
    buck[t].upd();
    return buck[t].size;
}
void add(int diff){
    int t=0;
    for(;t<=mg;t++)if(buck[t].val[buck[t].size-1]>=diff)break;
    if(t>mg)t--;
    int idx=upper_bound(buck[t].val,buck[t].val+buck[t].size,diff)-buck[t].val;
    for(int i=buck[t].size;i>idx;i--)buck[t].val[i]=buck[t].val[i-1];
    buck[t].val[idx]=diff;
    buck[t].size++;
    buck[t].upd();
}
int answer(){
    int last=buck[0].last[0];
    int cnt=buck[0].cnt[0];
    for(int g=1;g<=mg;g++){
        if(buck[g].val[buck[g].size-1]<=last)continue;
        int t=upper_bound(buck[g].val,buck[g].val+buck[g].size,last)-buck[g].val;
        cnt+=buck[g].cnt[t];
        last=buck[g].last[t];
    }
    return cnt;
}
void init(int n, int L, int tmp[])
{
    l=L;
    int t=sz;
    for(int i=0;i<n;i++){
        arr[i]=tmp[i];
        if(i==t) t+=sz,mg++;
        cin>>arr[i];
        buck[mg].val[i-t+sz]=arr[i];
        buck[mg].size++;
    }
    for(int i=0;i<=mg;i++){
        buck[mg].upd();
    }
}

int update(int a, int b)
{
    upcnt++;
    if(upcnt==sz) refresh();
    if(!remove(arr[a]))refresh();
    add(b);
    arr[a]=b;
    return answer();
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Incorrect 20 ms 2176 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Incorrect 20 ms 2176 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Incorrect 20 ms 2176 KB Output isn't correct
8 Halted 0 ms 0 KB -