Submission #485371

#	Time	Username	Problem	Language	Result	Execution time	Memory
485371		blue	Dancing Elephants (IOI11_elephants)	C++17	26 / 100	27 ms	1508 KiB

elephants

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

const long long maxN = 150'000;
// const long long rt = 1000; //change value and check

const long long block_count = 500;
const long long block_size = 500;
const long long recompute_freq = 100;

//block_size * block_count >= maxN


using vi = vector<long long>;

long long N;
long long L;
long long* X;
long long* I;

void init(int N_, int L_, int X_[])
{
    N = N_;
    L = L_;
    X = new long long[N];
    for(long long i = 0; i < N; i++) X[i] = X_[i];

    I = new long long[N];
    for(long long i = 0; i < N; i++) I[i] = i;

    // cerr << "check\n";
    // cerr << "L = " << L << '\n';
}

long long sz[block_count];
long long blocklist[block_count][block_size + recompute_freq];
long long block[5 + maxN];

long long camera_count[5 + maxN];
long long camera_reach[5 + maxN];

void compute_block(long long b)
{
    sort(blocklist[b], blocklist[b] + sz[b], [] (long long u, long long v)
    {
        return X[u] < X[v];
    });

    long long r = sz[b] - 1;
    for(long long l = sz[b] - 1; l >= 0; l--)
    {
        while(X[blocklist[b][r]] - X[blocklist[b][l]] > L)
            r--;

        if(r == sz[b] - 1)
        {
            camera_count[blocklist[b][l]] = 1;
            camera_reach[blocklist[b][l]] = X[blocklist[b][l]] + L;
        }
        else
        {
            camera_count[blocklist[b][l]] = 1 + camera_count[blocklist[b][r+1]];
            camera_reach[blocklist[b][l]] = camera_reach[blocklist[b][r+1]];
        }
    }
}

void rebuild()
{
    sort(I, I+N, [] (long long p, long long q)
    {
        return X[p] < X[q];
    });

    for(long long q = 0; q < block_count; q++)
        sz[q] = 0;

    for(long long x = 0; x < N; x++)
    {
        long long i = I[x];
        block[i] = x/block_size;
        blocklist[x/block_size][x%block_size] = i;
        sz[x/block_size]++;
    }



    for(long long b = 0; b < block_count; b++)
        compute_block(b);
}




void erase_elephant(long long oldblock, long long i)
{
    for(long long f = 0; f+1 < sz[oldblock]; f++)
    {
        if(blocklist[oldblock][f] == i)
            swap(blocklist[oldblock][f], blocklist[oldblock][f+1]);
    }

    sz[oldblock]--;
    compute_block(oldblock);
}

void insert_elephant(long long newblock, long long i)
{
    block[i] = newblock;
    sz[newblock]++;
    blocklist[newblock][sz[newblock]-1] = i;
    compute_block(newblock);
}


void change_X(long long i, long long y)
{
    long long oldblock = block[i];

    long long newblock = -1;
    long long newblock_score = 2'000'000'001;
    for(long long b = 0; b < block_count; b++)
    {
        if(!sz[b]) continue;

        long long curr_score = abs(X[blocklist[b][0]] - y) + abs(X[blocklist[b][sz[b] - 1]] - y);
        if(curr_score < newblock_score)
        {
            newblock = b;
            newblock_score = curr_score;
        }
    }

    long long oldX = X[i];

    X[i] = y;

    erase_elephant(oldblock, i);
    insert_elephant(newblock, i);
}

long long answer()
{
    long long res = 0;
    long long b = 0;
    while(sz[b] == 0) b++;

    long long st = blocklist[b][0];
    while(1)
    {
        // cerr << "st = " << st << '\n';
        long long rc = camera_reach[st];
        res += camera_count[st];

        bool nonext = 0;

        while(1)
        {
            if(b >= block_count)
            {
                nonext = 1;
                break;
            }

            if(sz[b] == 0)
            {
                b++;
                continue;
            }

            if(X[blocklist[b][sz[b] - 1]] <= rc)
            {
                b++;
                continue;
            }

            break;
        }

        // cerr << "b = " << b << '\n';
        // cerr << X[blocklist[b][sz[b] - 1]] << '\n';

        if(nonext) return res;

        long long lo = 0;
        long long hi = sz[b] - 1;
        while(lo != hi)
        {
            long long mid = (lo+hi)/2;
            if(X[blocklist[b][mid]] <= rc) lo = mid+1;
            else hi = mid;
        }

        st = blocklist[b][lo];
    }


    return -1;
}

long long u_ct = -1;
int update(int i, int y)
{
    // cerr << "starting update\n";
    u_ct++;
    if(u_ct % recompute_freq == 0)
    {
        X[i] = y;
        rebuild();
    }
    else
    {
        change_X(i, y);
    }

// cerr << "ending update\n";
    return answer();
}

Compilation message (stderr)

elephants.cpp: In function 'void change_X(long long int, long long int)':
elephants.cpp:137:15: warning: unused variable 'oldX' [-Wunused-variable]
  137 |     long long oldX = X[i];
      |               ^~~~

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