Submission #1030904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030904		idas	Dancing Elephants (IOI11_elephants)	C++11	100 / 100	6836 ms	28088 KiB

elephants

#include "elephants.h"

#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define pb push_back
#define s second
#define f first

using namespace std;
typedef pair<int, int> pii;

const int MxN=150001, C=388, INF=1e9;

int n, l, x[MxN], dp[MxN], far[MxN], gr[MxN], max_block;
vector<pii> block[C];

void build_block(int in)
{
    int j=block[in].size();
    for(int k=block[in].size()-1; k>=0; k--){
        int i=block[in][k].s;
        while(j-1>k && block[in][j-1].f>x[i]+l) j--;
        if(j==block[in].size()) dp[i]=1, far[i]=x[i]+l;
        else{
            int nxt=block[in][j].s;
            dp[i]=dp[nxt]+1;
            far[i]=far[nxt];
        }
    }
}

void build()
{
    vector<pii> vec;
    FOR(i, 0, n) vec.pb({x[i],i});

    sort(vec.begin(), vec.end()); // might be possible to optimize this

    FOR(i, 0, max_block+1) block[i].clear();

    max_block=0;
    FOR(i, 0, n)
    {
        int in=i/C;
        block[in].pb(vec[i]);
        gr[vec[i].s]=in;
        max_block=max(max_block, in);
    }

    FOR(i, 0, max_block+1) build_block(i);
}

void change_pos(int i, int y)
{
    int in=gr[i];
    block[in].erase(lower_bound(block[in].begin(), block[in].end(), make_pair(x[i],i)));
    build_block(in);

    x[i]=y;

    int nxt_in=0;
    FOR(id, 0, max_block+1) // might be possible to optimize this
    {
        if(block[id].empty()) continue;
        if(block[id][0].f<=x[i]) nxt_in=id;
    }

    gr[i]=nxt_in;
    block[nxt_in].insert(upper_bound(block[nxt_in].begin(), block[nxt_in].end(), make_pair(x[i],i)), {x[i],i});
    build_block(nxt_in);
}

int answer()
{
    int farr=-1, ret=0;
    FOR(i, 0, max_block+1)
    {
        if(block[i].empty() || block[i].back().f<=farr) continue;

        int l0=0, r0=block[i].size();
        while(l0<r0){
            int m=(l0+r0)/2;
            if(block[i][m].f>farr) r0=m;
            else l0=m+1;
        }

//        cout << i << ": " << l0 << '\n';

        assert(l0<block[i].size());

        assert(block[i][l0].f>farr);

        ret+=dp[block[i][l0].s];
        farr=far[block[i][l0].s];
    }
    return ret;
}

void print_block(int in)
{
    for(auto it : block[in]){
        cout << it.f << " " << it.s << '\n';
    }
}

void print_blocks()
{
    FOR(i, 0, max_block+1)
    {
        cout << "block " << i << ":\n";
        print_block(i);
    }
}

void init(int N, int L, int X[])
{
    n=N; l=L; FOR(i, 0, n) x[i]=X[i];
}

int counter=0;
int update(int i, int y)
{
    if(counter%C==0) build();
    change_pos(i, y);
    counter++;

//    cout << "update (" << i << ", " << y << "):\n";
//
//    print_blocks();

    return answer();
}

Compilation message (stderr)

elephants.cpp: In function 'void build_block(int)':
elephants.cpp:23:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         if(j==block[in].size()) dp[i]=1, far[i]=x[i]+l;
      |            ~^~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from elephants.cpp:3:
elephants.cpp: In function 'int answer()':
elephants.cpp:89:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         assert(l0<block[i].size());
      |                ~~^~~~~~~~~~~~~~~~

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