제출 #887940

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
887940		12345678	코끼리 (Dancing Elephants) (IOI11_elephants)	C++17	97 / 100	9002 ms	25740 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=390;
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;
    deque<int> dq;
    dq.push_back(INT_MAX);
    for (int i=vl[x].size()-1; i>=0; i--)
    {
        while (dq.size()>=2)
        {
            auto tmp=dq.back();
            dq.pop_back();
            if (vl[x][dq.back()]<=vl[x][i]+l) 
            {
                dq.push_back(tmp);
                break; 
            }
        }
        if (dq.back()==INT_MAX) 
        {
            dp[x][i].first=vl[x][i]+l;
            dp[x][i].second=1;
        }
        else
        {
            dp[x][i].first=dp[x][dq.back()].first;
            dp[x][i].second=dp[x][dq.back()].second+1;
        }
        dq.push_front(i);
        //if (cnt==5) cout<<x<<' '<<i<<' '<<vl[x][i]<<' '<<dp[x][i].first<<' '<<dp[x][i].second<<'\n';
    }
}
 
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;
        //if (cnt==5) cout<<i<<' '<<res<<' '<<lst<<'\n';
    }
    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 ((++cnt)%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