oj.uz

Submission #220510

# Submission time Handle Problem Language Result Execution time Memory
220510 2020-04-08T02:55:24 Z anonymous Dancing Elephants (IOI11_elephants) C++14
26 / 100
 9000 ms 7932 KB 
                #include "elephants.h"
                #include <iostream>
                #include <set>
                #include <utility>
                #include <cassert>
                #define MAXN 70005
                #define K 265
                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 4 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 4 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
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 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 431 ms 2688 KB Output is correct
8 Correct 547 ms 3448 KB Output is correct
9 Correct 2558 ms 7928 KB Output is correct
10 Correct 1227 ms 7928 KB Output is correct
11 Correct 1578 ms 7932 KB Output is correct
12 Execution timed out 9072 ms 7928 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 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 431 ms 2688 KB Output is correct
8 Correct 547 ms 3448 KB Output is correct
9 Correct 2558 ms 7928 KB Output is correct
10 Correct 1227 ms 7928 KB Output is correct
11 Correct 1578 ms 7932 KB Output is correct
12 Execution timed out 9072 ms 7928 KB Time limit exceeded
13 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 4 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 431 ms 2688 KB Output is correct
8 Correct 547 ms 3448 KB Output is correct
9 Correct 2558 ms 7928 KB Output is correct
10 Correct 1227 ms 7928 KB Output is correct
11 Correct 1578 ms 7932 KB Output is correct
12 Execution timed out 9072 ms 7928 KB Time limit exceeded
13 Halted 0 ms 0 KB -