Submission #769255

#	Time	Username	Problem	Language	Result	Execution time	Memory
769255		Dan4Life	Dancing Elephants (IOI11_elephants)	C++17	97 / 100	9040 ms	16260 KiB

elephants

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define lb lower_bound
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
using ar = array<int,2>;
const int mxN = 150010;
const int B = 400;
int n, L, a[mxN];
unordered_map<int,int> cnt;
 
struct Block{
    vector<int> V; ar V2[B+3];
    Block(){}
    void recalc(){
        for(int i = sz(V)-1; i>=0; i--){
            int pos = lb(begin(V)+i,end(V),V[i]+L+1)-begin(V);
            if(pos==sz(V)) V2[i]=ar({1,V[i]+L+1});
            else V2[i]=ar({V2[pos][0]+1,V2[pos][1]});
        }
    }
    Block(vector<int> XD){ V.swap(XD); recalc(); }
    void add(int x){
        if(++cnt[x]!=1) return;
        V.insert(lb(all(V),x),x); recalc();
    }
    void rem(int x){ 
        if(--cnt[x]) return;
        V.erase(lb(all(V),x)); recalc(); 
    }
};
vector<Block> bl;
 
bool combine(int i, int j){
    if(i>j) swap(i,j); 
    int SZ = sz(bl[i].V)+sz(bl[j].V);
    if(SZ>B) return 0; vector<int> V3(SZ);
    merge(all(bl[i].V),all(bl[j].V),begin(V3));
    bl[i]=Block(V3), bl.erase(begin(bl)+j); return 1;
} 
 
void divide(int i){
    int mid = sz(bl[i].V)/2; if(mid*2<B) return;
    auto B1 = Block(vector<int>(begin(bl[i].V),begin(bl[i].V)+mid));
    auto B2 = Block(vector<int>(begin(bl[i].V)+mid,end(bl[i].V)));
    bl.insert(begin(bl)+i+1,B2); bl[i]=B1;
}
 
void init(int N, int l, int A[]){
    bl.push_back({}); L = l; n = N;
    for(int i = 0; i < n; i++)
        a[i] = A[i], bl.back().add(a[i]), divide(sz(bl)-1);
}
 
int findBl(int x){
    int l = 0, r = sz(bl)-1;
    while(l<r){
        int mid = (l+r)/2;
        if(bl[mid].V.back()<x) l=mid+1;
        else r=mid;
    }
    return l;
}
 
int update(int p, int y){
    int i = findBl(a[p]);
    bl[i].rem(a[p]); 
    int xd = i;
    while(i and combine(i-1,i)) i--;
    i = xd; while(i<sz(bl)-1 and combine(i,i+1)) i;
    a[p] = y; i = findBl(a[p]); bl[i].add(a[p]); divide(i);
    int ans = 0, pos = 0;
    for(Block cur : bl){
        if(!sz(cur.V) or cur.V.back()<pos) continue;
        auto p = lb(all(cur.V),pos)-begin(cur.V);
        ans+=cur.V2[p][0], pos = cur.V2[p][1];
    }
    return ans;
}

Compilation message (stderr)

elephants.cpp: In function 'bool combine(int, int)':
elephants.cpp:40:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   40 |     if(SZ>B) return 0; vector<int> V3(SZ);
      |     ^~
elephants.cpp:40:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   40 |     if(SZ>B) return 0; vector<int> V3(SZ);
      |                        ^~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:73:50: warning: statement has no effect [-Wunused-value]
   73 |     i = xd; while(i<sz(bl)-1 and combine(i,i+1)) i;
      |                                                  ^
elephants.cpp: In function 'void init(int, int, int*)':
elephants.cpp:15:8: warning: '<anonymous>.Block::V2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   15 | struct Block{
      |        ^~~~~

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