Submission #808994

#	Time	Username	Problem	Language	Result	Execution time	Memory
808994		TheSahib	Dancing Elephants (IOI11_elephants)	C++14	97 / 100	9068 ms	12492 KiB

elephants

#pragma GCC optimize("O3")

#include "elephants.h"
#include <bits/stdc++.h>

#define pii pair<int, int>

using namespace std;

const int oo = 1e9 + 9;
const int MAX = 150005;
const int BLOCK = 380;


int n, l;
vector<int> st;
int arr[MAX];


struct DATA{
    vector<int> v;
    vector<pii> dp;
    void update(int a, bool b){
        auto itr = lower_bound(v.begin(), v.end(), a);
        if(b){
            v.insert(itr, a);
        }
        else{
            v.erase(itr);
        }
    }
    void calc(){
        dp.resize(v.size());
        for(int i = v.size() - 1; i >= 0; --i){
            int j = upper_bound(v.begin(), v.end(), v[i] + l) - v.begin();
            if(j == v.size()){
                dp[i] = {1, v[i] + l};
            }
            else{
                dp[i] = dp[j];
                dp[i].first += 1;
            }
        }
    }
};

int blockCnt = 0;
DATA blocks[MAX / BLOCK + 1];

void build(){
    vector<int> v(n);
    for (int i = 0; i < n; i++)
    {
        v[i] = arr[i];
    }
    sort(v.begin(), v.end());
    for(int i = 0; i < blockCnt; i++){
        blocks[i].v.clear();
    }
    for(int i = 0; i < n; ++i){
        blocks[i / BLOCK].v.push_back(v[i]);
    }
    for(int i = 0; i < blockCnt; i++){
        sort(blocks[i].v.begin(), blocks[i].v.end());
        blocks[i].calc();
    }
}

int findBlock(int a){
    int l = 0, r = blockCnt - 1;
    int ans = 0;
    while(l <= r){
        int mid = (l + r) / 2;
        int mn = oo;
        if(!blocks[mid].v.empty()){
            mn = blocks[mid].v[0];
        }

        if(a < mn){
            r = mid - 1;
        }
        else{
            ans = mid;
            l = mid + 1;
        }
    }
    return ans;
}

void init(int N, int L, int X[])
{
    n = N;
    l = L;
    blockCnt = (N + BLOCK - 1) / BLOCK;
    for(int i = 0; i < N; ++i){
        arr[i] = X[i];
    }
    build();
}

int q = 0;

int update(int i, int y)
{
    q += 1;
    if(q >= BLOCK - 1){
        arr[i] = y;
        build();
        q = 0;
    }
    else{
        int a = findBlock(arr[i]);
        int b = findBlock(y);
        blocks[a].update(arr[i], 0);
        blocks[b].update(y, 1);
        arr[i] = y;
        blocks[a].calc();
        blocks[b].calc();
    }
    int p = -1;
    int ans = 0;
    for(int i = 0; i < blockCnt; ++i){
        if(blocks[i].v.back() <= p) continue;
        int idx = upper_bound(blocks[i].v.begin(), blocks[i].v.end(), p) - blocks[i].v.begin();
        ans += blocks[i].dp[idx].first;
        p = blocks[i].dp[idx].second;
    }
    return ans;
}

Compilation message (stderr)

elephants.cpp: In member function 'void DATA::calc()':
elephants.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |             if(j == v.size()){
      |                ~~^~~~~~~~~~~

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