Submission #220505

#	Time	Username	Problem	Language	Result	Execution time	Memory
220505		anonymous	Dancing Elephants (IOI11_elephants)	C++14	26 / 100	9082 ms	7980 KiB

elephants

            #include "elephants.h"
            #include <iostream>
            #include <set>
            #include <utility>
            #include <cassert>
            #define MAXN 50005
            #define K 225
            using namespace std;
             
            int N, L, Q, Pos[MAXN], Prev[MAXN];
            bool stray[MAXN];
            multiset <pair <int,int> > E, G, S; //all elephants: pos = id and ghost: pos = id
            int nxt[MAXN][20];
             
            void makeJump() {
                for (int i=0; i<=N; i++) {
                    auto it = E.upper_bound({Pos[i] + L,MAXN});
                    if (it == E.end()) {
                        nxt[i][0] = N;
                    } else {
                        nxt[i][0] = (*it).second;
                    }
                    //printf("%d %d\n",i,nxt[i][0]);
                }
                for (int i=1; i<20; i++) {
                    for (int j=0; j<=N; j++) {
                        nxt[j][i] = nxt[nxt[j][i-1]][i-1];
                    }
                }
            }
             
            int Next(int p) {
                auto it = E.upper_bound({p + L,MAXN});
                if (it == E.end()) {
                    return(N);
                } else {
                    return((*it).second);
                }
            }
             
            void init(int n, int l, int x[])
            {
              N= n, L = l;
              for (int i=0; i<n; i++) {
                Pos[i] = x[i];
                Prev[i] = x[i];
                E.insert({x[i], i});
              }
              E.insert({(int) 2e9 + 5, N}); //dummy
              Prev[N] = Pos[N] = (int)  2e9 + 5;
              makeJump();
            }
             
            int update(int i, int y)
            {
              Q+=1;
              if (stray[i]) {
                 S.erase(S.find({Pos[i], i}));
              } else {
                 G.insert({Pos[i], i}); //old pos as considered in jump
                 stray[i] = true;
              }
              E.erase(E.find({Pos[i], i}));
              E.insert({y, i});
              S.insert({y, i});
              Pos[i] = y;
              if (Q%K == 0) {
                G.clear();
                S.clear();
                for (int i=0; i<N; i++) {
                    stray[i] = 0;
                    Prev[i] = Pos[i];
                }
                makeJump();
              }
              int at = (*E.begin()).second, prev_at = -1, Ans = 0;
              while (at != N) {
                   prev_at = at;
                   if (stray[at]) {
                       Ans+=1;
                       at = Next(Pos[at]);
                   } else {
                       if (G.upper_bound({Pos[at]+L,MAXN}) == G.end() && S.upper_bound({Pos[at]+L,MAXN}) == S.end()) {
                            for (int i = 19; i >= 0; i--) {
                                if (nxt[at][i] != N) {
                                    at = nxt[at][i];
                                    Ans += (1<<i);
                                }
                            }
                            Ans+=1;
                            //Jump 1 more
                            //assert(nxt[at][0] == N && at != N);
                            break;
                       } else  {
                            int CritPos = 0;
                            if (S.upper_bound({Pos[at]+L,MAXN}) == S.end() || (*G.upper_bound({Pos[at]+L,MAXN})).first < (*S.upper_bound({Pos[at]+L,MAXN})).first) {
                                CritPos = (*G.upper_bound({Pos[at]+L,MAXN})).first;
                            } else {
                                CritPos = (*S.upper_bound({Pos[at]+L,MAXN})).first;
                            }
                            for (int i = 19; i >= 0; i--) {
                                if (Prev[nxt[at][i]] < CritPos && !stray[nxt[at][i]]) {
                                    at = nxt[at][i];
                                    Ans += (1<<i);
                                }
                            }
                            Ans+=1;
                            at = Next(Pos[at]);
                       }
                   }
                   // assert (at != prev_at);
              }
              return(Ans);
            }

Compilation message (stderr)

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:76:45: warning: variable 'prev_at' set but not used [-Wunused-but-set-variable]
               int at = (*E.begin()).second, prev_at = -1, Ans = 0;
                                             ^~~~~~~

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