Submission #220516

#	Time	Username	Problem	Language	Result	Execution time	Memory
220516		anonymous	Dancing Elephants (IOI11_elephants)	C++14	50 / 100	9048 ms	7960 KiB

elephants

  #include "elephants.h"
                #include <iostream>
                #include <set>
                #include <utility>
                #include <cassert>
                #define MAXN 70005
                #define K 250
                #define LOG 16
                using namespace std;

                int N, L, Q, Pos[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<=LOG; 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];
                    E.insert({x[i], i});
                  }
                  E.insert({(int) 2e9 + 5, N}); //dummy
                  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) {
                    for (auto i: S) {
                        stray[i.second] = 0;
                    }
                    G.clear();
                    S.clear();
                    makeJump();
                  }
                  int at = (*E.begin()).second, prev_at = -1, Ans = 0;
                  while (at != N) {
                       if (stray[at]) {
                           Ans+=1;
                           at = Next(Pos[at]);
                       } else {
                           auto itG = G.upper_bound({Pos[at]+L,MAXN}) ;
                           auto itS = S.upper_bound({Pos[at]+L,MAXN}) ;
                           if (itG == G.end() && itS == S.end()) {
                                for (int i = LOG; 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 (itS == S.end() ||  (itG != G.end() && (*itG).first < (*itS).first)) {
                                    CritPos = (*itG).first;
                                } else {
                                    CritPos = (*itS).first;
                                }
                                for (int i = LOG; i >= 0; i--) {
                                    if (Pos[nxt[at][i]] <= CritPos && !stray[nxt[at][i]]) {
                                        at = nxt[at][i];
                                        Ans += (1<<i);
                                    }
                                }
                                Ans+=1;
                                at = Next(Pos[at]);
                           }
                       }
                  }
                  return(Ans);
                }

Compilation message (stderr)

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:75:49: warning: unused variable 'prev_at' [-Wunused-variable]
                   int at = (*E.begin()).second, prev_at = -1, Ans = 0;
                                                 ^~~~~~~

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