Submission #769246

#	Time	Username	Problem	Language	Result	Execution time	Memory
769246		Dan4Life	Dancing Elephants (IOI11_elephants)	C++17	97 / 100	9064 ms	16328 KiB

elephants

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front
#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 = 700;
int n, L, a[mxN];
unordered_map<int,int> cnt;
 
struct Block{
    vector<int> V; ar V2[B+10];
    Block(){V.clear();}
    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;
 
void 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; vector<int> V3(SZ);
    merge(all(bl[i].V),all(bl[j].V),begin(V3));
    bl[i]=Block(V3), bl.erase(begin(bl)+j);
} 
 
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.pb({}); 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 update(int p, int y){
    for(int i = 0; i < sz(bl); i++){
        if(bl[i].V.back()>=a[p]){ 
            bl[i].rem(a[p]); 
            if(i) combine(i-1,i);
            if(i<sz(bl)-1) combine(i,i+1);
            break;
        }
    }
    a[p] = y;
    for(int i = 0; i < sz(bl); i++){
        if(i==sz(bl)-1 or bl[i].V.back() >= a[p]){
            bl[i].add(a[p]); divide(i); break;
        }
    }
    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 'void combine(int, int)':
elephants.cpp:39:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   39 |     if(SZ>B) return; vector<int> V3(SZ);
      |     ^~
elephants.cpp:39:22: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   39 |     if(SZ>B) return; vector<int> V3(SZ);
      |                      ^~~~~~
elephants.cpp: In function 'void init(int, int, int*)':
elephants.cpp:14:8: warning: '<anonymous>.Block::V2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   14 | struct Block{
      |        ^~~~~

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