oj.uz

Submission #220509

# Submission time Handle Problem Language Result Execution time Memory
220509 2020-04-08T02:54:06 Z anonymous Dancing Elephants (IOI11_elephants) C++14
50 / 100
 9000 ms 9848 KB 
                #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],MAXN}) == G.end() && S.upper_bound({Pos[at],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],MAXN}) == S.end() ||  (G.upper_bound({Pos[at], MAXN}) != G.end() && (*G.upper_bound({Pos[at], MAXN})).first < (*S.upper_bound({Pos[at],MAXN})).first)) {
                                    CritPos = (*G.upper_bound({Pos[at],MAXN})).first;
                                } else {
                                    CritPos = (*S.upper_bound({Pos[at],MAXN})).first;
                                }
                                for (int i = 19; 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]);
                                //assert (at != prev_at);
                           }
                       }
                  }
                  return(Ans);
                }

Compilation message

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:76:49: 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 460 ms 2808 KB Output is correct
8 Correct 586 ms 3448 KB Output is correct
9 Correct 2475 ms 8068 KB Output is correct
10 Correct 1436 ms 7928 KB Output is correct
11 Correct 1719 ms 9336 KB Output is correct
12 Correct 8663 ms 9464 KB Output is correct
13 Correct 1394 ms 9040 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 460 ms 2808 KB Output is correct
8 Correct 586 ms 3448 KB Output is correct
9 Correct 2475 ms 8068 KB Output is correct
10 Correct 1436 ms 7928 KB Output is correct
11 Correct 1719 ms 9336 KB Output is correct
12 Correct 8663 ms 9464 KB Output is correct
13 Correct 1394 ms 9040 KB Output is correct
14 Correct 2982 ms 5240 KB Output is correct
15 Correct 1144 ms 6008 KB Output is correct
16 Execution timed out 9054 ms 9848 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 460 ms 2808 KB Output is correct
8 Correct 586 ms 3448 KB Output is correct
9 Correct 2475 ms 8068 KB Output is correct
10 Correct 1436 ms 7928 KB Output is correct
11 Correct 1719 ms 9336 KB Output is correct
12 Correct 8663 ms 9464 KB Output is correct
13 Correct 1394 ms 9040 KB Output is correct
14 Correct 2982 ms 5240 KB Output is correct
15 Correct 1144 ms 6008 KB Output is correct
16 Execution timed out 9054 ms 9848 KB Time limit exceeded
17 Halted 0 ms 0 KB -