oj.uz

Submission #770593

# Submission time Handle Problem Language Result Execution time Memory
770593 2023-07-01T13:46:25 Z adrilen Dancing Elephants (IOI11_elephants) C++17
26 / 100
 9000 ms 6640 KB 
#include "elephants.h"
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using arr = array<int, 2>;
using arrr = array<int, 3>;

constexpr int maxn = 1.5e5, min_size = 20, max_size = 80, start_size = 2, num_groups = maxn / start_size + 1;

int n, l;

struct Group {
    int n;
    vector <int> pos;
    vector <arr> pref;

    void calc()             // O(sqrt(n) log n)
    {
        assert(n == (int)pos.size());
        pref.resize(n + 1);

        pref[n] = {0, 0};
        sort(pos.begin(), pos.end());

        for (int p = n - 1; p >= 0; p--)
        {
            int ind = upper_bound(pos.begin(), pos.end(), pos[p] + l) - pos.begin();    
            
            pref[p] = {pref[ind][0] + 1, max(pos[p] + l, pref[ind][1])};
        }
    }

    void insert(int p, bool up = false)     // O(sqrt(n))
    {
        pos.emplace_back(p);
        n++;
        if (up) calc();
    }

    void erase(int p, bool up = false)      // O(sqrt(n))
    {
        n--;
        pos.erase(lower_bound(pos.begin(), pos.end(), p));

        if (up) calc();
    }

} ;

Group groups[num_groups];

int last_group;

int get_total()                         // O(n / sqrt(n) log n)
{
    int output = 0;

    int last_length = -1;
    for (int i = 0; i < last_group; i++)
    {
        // if (groups[i].n == 0) continue;
        int pos = upper_bound(groups[i].pos.begin(), groups[i].pos.end(), last_length) - groups[i].pos.begin();

        output += groups[i].pref[pos][0];
        last_length = max(last_length, groups[i].pref[pos][1]);
    }

    return output;
}


int ind_to_pos[maxn] = { 0 };
void init(int N, int L, int X[])            // O(n / sqrt(n))
{
    n = N, l = L;

    for (int i = 0; i < n; i++) ind_to_pos[i] = X[i];


    for (int y = 0; y <= n / start_size; y++)
    {
        for (int i = 0; i < start_size; i++)
        {
            if (y * start_size + i == n) {
                y = 2e9;
                break;
            }
            groups[y].insert(X[y * start_size + i]);
        }
    }

    int y;
    for ( y = 0; y < num_groups; y++)
    {
        if (groups[y].n == 0) break;
        groups[y].calc();
    }
    last_group = y;
}



int update(const int i, int y)
{
    int u = ind_to_pos[i]; // Now position

    int j;
    for (j = 0; (groups[j].n == 0 || groups[j].pos.back() < u) && j + 1 < last_group; j++) ;

    assert(j != last_group && "ERROR");


    groups[j].erase(u, true);

    ind_to_pos[i] = y;

    for (j = 0; (groups[j].n == 0 || groups[j].pos.back() < y) && j + 1 < last_group; j++);
    assert(j != last_group && "ERROR");

    groups[j].insert(y, true);
    

    // cout<< "i\n";
    // for (int a = 0; a < 5; a++) {
    //     if (groups[a].n == 0) continue;
    //     for (int o = 0; o <= groups[a].n; o++)
    //     {

    //         cout << groups[a].pref[o][0] << " " << groups[a].pref[o][1] << "\t";
    //     }
    //     cout << endl;
    // }
    // cout << endl;

    // for (int a = 0; a < 5; a++) {
    //     if (groups[a].n == 0) continue;
    //     for (int o = 0; o <= groups[a].n; o++)
    //     {
    //         cout << groups[a].pos[o] << "\t";
    //     }
    //     cout << endl;
    // }
    // cout << endl;

    // cout << "o\n";    


    return get_total();
}


/*
g++ -o $PROBLEM grader.cpp $PROBLEM.cpp -fsanitize="address","undefined" -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC -Wall -g3 -O2 && ./$PROBLEM
g++ -o $PROBLEM grader.cpp $PROBLEM.cpp -Wall -g3 && ./$PROBLEM


*/

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4436 KB Output is correct
2 Correct 2 ms 4436 KB Output is correct
3 Correct 3 ms 4436 KB Output is correct
4 Correct 2 ms 4428 KB Output is correct
5 Correct 2 ms 4432 KB Output is correct
6 Correct 3 ms 4436 KB Output is correct
7 Execution timed out 9056 ms 6640 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4436 KB Output is correct
2 Correct 2 ms 4436 KB Output is correct
3 Correct 3 ms 4436 KB Output is correct
4 Correct 2 ms 4428 KB Output is correct
5 Correct 2 ms 4432 KB Output is correct
6 Correct 3 ms 4436 KB Output is correct
7 Execution timed out 9056 ms 6640 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4436 KB Output is correct
2 Correct 2 ms 4436 KB Output is correct
3 Correct 3 ms 4436 KB Output is correct
4 Correct 2 ms 4428 KB Output is correct
5 Correct 2 ms 4432 KB Output is correct
6 Correct 3 ms 4436 KB Output is correct
7 Execution timed out 9056 ms 6640 KB Time limit exceeded
8 Halted 0 ms 0 KB -