Submission #887693

#	Time	Username	Problem	Language	Result	Execution time	Memory
887693		12345678	Dancing Elephants (IOI11_elephants)	C++17	97 / 100	5869 ms	33620 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;

const int nx=150005, tx=380;
int n, c[nx], v[nx], l, cnt;
multiset<int> ms[tx];
vector<int> vl[tx];
vector<pair<int, int>> dp[tx];

void calc(int x)
{
    vl[x].resize(0);
    for (auto a:ms[x]) vl[x].push_back(a);
    dp[x].resize(vl[x].size());
    if (vl[x].size()==0) return;
    for (int i=vl[x].size()-1; i>=0; i--)
    {
        if (upper_bound(vl[x].begin(), vl[x].end(), vl[x][i]+l)==vl[x].end())
        {
            dp[x][i].first=vl[x][i]+l;
            dp[x][i].second=1;
        }
        else
        {
            int idx=upper_bound(vl[x].begin(), vl[x].end(), vl[x][i]+l)-vl[x].begin();
            dp[x][i].first=dp[x][idx].first;
            dp[x][i].second=dp[x][idx].second+1;
        }
    }
}

void build()
{
    vector<pair<int, int>> d(n);
    for (int i=0; i<n; i++) d[i].first=v[i], d[i].second=i;
    sort(d.begin(), d.end());
    for (int i=0; i<tx; i++) ms[i].clear();
    for (int i=0; i<n; i++) c[d[i].second]=i/tx, ms[i/tx].insert(d[i].first);
    for (int i=0; i<tx; i++) calc(i);
}

int query()
{
    int lst=-1, res=0;
    for (int i=0; i<tx; i++)
    {
        if (vl[i].empty()||lst>=vl[i][vl[i].size()-1]) continue;
        int idx=upper_bound(vl[i].begin(), vl[i].end(), lst)-vl[i].begin();
        res+=dp[i][idx].second;
        lst=dp[i][idx].first;
    }
    return res;
}

void init(int N, int L, int X[])
{
    n=N; l=L;
    for (int i=0; i<n; i++) v[i]=X[i];
    build();
}

int update(int i, int y)
{
    if (i%tx==0) 
    {
        v[i]=y;
        build();
        return query();
    }
    int loc=c[i];
    ms[loc].erase(ms[loc].find(v[i]));
    v[i]=y;
    calc(loc);
    for (int j=0; j<tx; j++)
    {
        if (j==tx-1)
        {
            ms[j].insert(y);
            c[i]=j;
            calc(j);
        }
        else if (!vl[j].empty()&&vl[j][vl[j].size()-1]>=y)
        {
            ms[j].insert(y);
            c[i]=j;
            calc(j);
            break;
        }
    }
    return query();
}

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