Submission #1085187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085187		Wansur	Dancing Elephants (IOI11_elephants)	C++17	97 / 100	9008 ms	40236 KiB

elephants

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

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

using namespace std;
const int maxn = 2e5 + 12;

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

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

void init(int N, int L, int X[]){
    n = N, l = L;
    k = 800;
    for(int i=0;i<n;i++){
        a[i] = X[i];
    }
    sort(a, a+n);
    for(int i=0;i<n;i++){
        q.insert({a[i], i});
        cnt[a[i]]++;
        if(cnt[a[i]] > 1) continue;
        is[i] = 1;
        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++;
        }
    }
    for(int i=0;i<=last;i++){
        calc(g[i]);
    }
}

void del(int i){
    q.erase({a[i], i});
    cnt[a[i]]--;
    if(cnt[a[i]] > 0){
        if(!is[i]) return;
        is[i] = 0;
        auto it = q.lower_bound({a[i], 0});
        for(int _=0;_<g[block[i]].size();_++){
            if(g[block[i]][_] == i){
                g[block[i]][_] = it -> second;
                block[it -> second] = block[i];
            }
        }
        is[it -> second] = 1;
        s.erase({a[i], i});
        s.insert(*it);
        calc(g[block[i]]);
        return;
    }
    is[i] = 0;
    int pos = -1;
    for(int _=0;_<g[block[i]].size();_++){
        if(g[block[i]][_] == i){
            pos = _;
        }
    }
    if(pos < 0) exit(0);
    g[block[i]].erase(g[block[i]].begin() + pos);
    calc(g[block[i]]);
    s.erase({a[i], i});
}

void add(int i){
    q.insert({a[i], i});
    cnt[a[i]]++;
    is[i] = 0;
    if(cnt[a[i]] > 1) return;
    is[i] = 1;
    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());
            block[g[bl].back()] = last;
            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:53:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |         if(g[last].size() >= k){
      |            ~~~~~~~~~~~~~~~^~~~
elephants.cpp: In function 'void del(int)':
elephants.cpp:69:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for(int _=0;_<g[block[i]].size();_++){
      |                     ~^~~~~~~~~~~~~~~~~~~
elephants.cpp:83:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int _=0;_<g[block[i]].size();_++){
      |                 ~^~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void add(int)':
elephants.cpp:117:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  117 |     if(g[bl].size() > k){
      |        ~~~~~~~~~~~~~^~~
elephants.cpp:119:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  119 |         while(g[bl].size() > k / 2){
      |               ~~~~~~~~~~~~~^~~~~~~

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