oj.uz

Submission #220513

# Submission time Handle Problem Language Result Execution time Memory
220513 2020-04-08T03:02:08 Z anonymous Dancing Elephants (IOI11_elephants) C++14
50 / 100
 9000 ms 8056 KB 
                #include "elephants.h"
                #include <iostream>
                #include <set>
                #include <utility>
                #include <cassert>
                #define MAXN 70005
                #define K 200
                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<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];
                    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],MAXN}) ;
                           auto itS = S.upper_bound({Pos[at]+L,MAXN}) ;
                           if (itG == G.end() && itS == 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 (itS == S.end() ||  (itG != G.end() && (*itG).first < (*itS).first)) {
                                    CritPos = (*itG).first;
                                } else {
                                    CritPos = (*itS).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]);
                           }
                       }
                  }
                  return(Ans);
                }

Compilation message

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:74:49: warning: unused variable 'prev_at' [-Wunused-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 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 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 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 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 462 ms 2688 KB Output is correct
8 Correct 603 ms 3448 KB Output is correct
9 Correct 2224 ms 7800 KB Output is correct
10 Correct 1574 ms 7684 KB Output is correct
11 Correct 1866 ms 8056 KB Output is correct
12 Correct 6836 ms 7720 KB Output is correct
13 Correct 1533 ms 7804 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 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 462 ms 2688 KB Output is correct
8 Correct 603 ms 3448 KB Output is correct
9 Correct 2224 ms 7800 KB Output is correct
10 Correct 1574 ms 7684 KB Output is correct
11 Correct 1866 ms 8056 KB Output is correct
12 Correct 6836 ms 7720 KB Output is correct
13 Correct 1533 ms 7804 KB Output is correct
14 Correct 2406 ms 3708 KB Output is correct
15 Correct 1146 ms 4472 KB Output is correct
16 Execution timed out 9093 ms 7928 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 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 462 ms 2688 KB Output is correct
8 Correct 603 ms 3448 KB Output is correct
9 Correct 2224 ms 7800 KB Output is correct
10 Correct 1574 ms 7684 KB Output is correct
11 Correct 1866 ms 8056 KB Output is correct
12 Correct 6836 ms 7720 KB Output is correct
13 Correct 1533 ms 7804 KB Output is correct
14 Correct 2406 ms 3708 KB Output is correct
15 Correct 1146 ms 4472 KB Output is correct
16 Execution timed out 9093 ms 7928 KB Time limit exceeded
17 Halted 0 ms 0 KB -