oj.uz

Submission #485317

# Submission time Handle Problem Language Result Execution time Memory
485317 2021-11-07T05:43:28 Z blue Dancing Elephants (IOI11_elephants) C++17
26 / 100
 9000 ms 1740 KB 
#include "elephants.h"
#include <vector>
#include <algorithm>
using namespace std;

const int maxN = 150'000;
const int rt = 100; //change value and check

using vi = vector<int>;

int N;
int L;
int* X;
int* I;

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

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

int sz[3'000];
int blocklist[3'000][3'000];
int block[5 + maxN];

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

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

    int r = sz[b] - 1;
    for(int 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, [] (int p, int q)
    {
        return X[p] < X[q];
    });

    for(int q = 0; q < 2*rt + 1; q++)
        sz[q] = 0;

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



    for(int b = 0; b < 2*rt + 5; b++)
        compute_block(b);
}




void erase_elephant(int oldblock, int i)
{
    for(int 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(int newblock, int i)
{
    block[i] = newblock;
    sz[newblock]++;
    blocklist[newblock][sz[newblock]-1] = i;
    compute_block(newblock);
}


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

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

        int 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;
        }
    }

    int oldX = X[i];

    X[i] = y;

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

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

    int st = blocklist[b][0];
    while(1)
    {
        int rc = camera_reach[st];
        res += camera_count[st];

        bool nonext = 0;

        while(1)
        {
            if(b >= 2*rt + 5)
            {
                nonext = 1;
                break;
            }

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

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

            break;
        }

        if(nonext) return res;

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

        st = X[blocklist[b][lo]];
    }


    return -1;
}

int u_ct = -1;
int update(int i, int y)
{
    u_ct++;
    if(u_ct % rt == 0)
    {
        X[i] = y;
        rebuild();
    }
    else
    {
        change_X(i, y);
    }

    return answer();
}

Compilation message

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

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Execution timed out 9058 ms 1740 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Execution timed out 9058 ms 1740 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Execution timed out 9058 ms 1740 KB Time limit exceeded
8 Halted 0 ms 0 KB -