Submission #1085116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085116		Wansur	Dancing Elephants (IOI11_elephants)	C++17	26 / 100	9059 ms	6288 KiB

elephants

#include <bits/stdc++.h>
#define ent '\n'

using namespace std;
const int maxn = 15e4 + 12;

set<pair<int, int>> s, t;
vector<int> g[maxn];
map<int, int> cnt;
int a[maxn], block[maxn];
int out[maxn], dp[maxn];
int n, k, l, last;

void init(int N, int L, int X[]){
    n = N, l = L;
    k = 350;
    for(int i=0;i<n;i++){
        a[i] = X[i];
    }
    sort(a, a+n);
    for(int i=0;i<n;i++){
        if(!g[last].size()){
            t.insert({a[i], last});
        }
        block[i] = last;
        g[last].push_back(i);
        s.insert({a[i], i});
        if(g[last].size() == k){
            last++;
        }
    }
}

void calc(vector<int> &c){
    for(int _=c.size()-1;_>=0;_--){
        int i = c[_];
        if(c.back() > a[i] + l){
            int pos = 0;
            for(int L = 0, R = c.size(); L <= R;){
                int mid = L + R >> 1;
                if(a[c[mid]] > a[i] + l){
                    pos = mid;
                    R = mid - 1;
                }
                else L = mid + 1;
            }
            out[i] = out[c[pos]];
            dp[i] = dp[c[pos]] + 1;
        }
        else{
            out[i] = a[i] + l;
            dp[i] = 1;
        }
    }
}

void del(int i){
    int pos = 0;
    for(int _=0;_<g[block[i]].size();_++){
        if(g[block[i]][_] == i){
            pos = _;
        }
    }
    g[block[i]].erase(g[block[i]].begin() + pos);
    calc(g[block[i]]);
    s.erase({a[i], i});
}

void add(int i){
    auto it = t.lower_bound({a[i] + 1, 0});
    int bl = 0;
    if(it == t.begin()){
        auto [x, y] = *it;
        t.erase(it);
        t.insert({a[i], y});
        bl = y;
    }
    else{
        it--;
        bl = it -> second;
    }
    block[i] = bl;
    g[bl].push_back(i);
    sort(g[bl].begin(), g[bl].end(), [](int i, int j){
        return a[i] < a[j];
    });
    if(g[bl].size() > k){
        last++;
        while(g[bl].size() > k / 2){
            g[last].push_back(g[bl].back());
            g[bl].pop_back();
        }
        reverse(g[last].begin(), g[last].end());
        t.insert({a[g[last][0]], last});
        calc(g[last]);
    }
    calc(g[bl]);
    s.insert({a[i], i});
}

int get(){
    int val = -1, ans = 0;
    while(1){
        auto it = s.lower_bound({val + 1, 0});
        if(it == s.end()) break;
        auto [x, y] = *it;
        ans += dp[y];
        val = out[y];
    }
    return ans;
}

int update(int i, int y){
    del(i);
    a[i] = y;
    add(i);
    return get();
}

Compilation message (stderr)

elephants.cpp: In function 'void init(int, int, int*)':
elephants.cpp:28:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |         if(g[last].size() == k){
      |            ~~~~~~~~~~~~~~~^~~~
elephants.cpp: In function 'void calc(std::vector<int>&)':
elephants.cpp:40:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |                 int mid = L + R >> 1;
      |                           ~~^~~
elephants.cpp: In function 'void del(int)':
elephants.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int _=0;_<g[block[i]].size();_++){
      |                 ~^~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void add(int)':
elephants.cpp:87:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   87 |     if(g[bl].size() > k){
      |        ~~~~~~~~~~~~~^~~
elephants.cpp:89:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |         while(g[bl].size() > k / 2){
      |               ~~~~~~~~~~~~~^~~~~~~

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