oj.uz

Submission #220514

# Submission time Handle Problem Language Result Execution time Memory
220514 2020-04-08T03:03:31 Z anonymous Dancing Elephants (IOI11_elephants) C++14
50 / 100
 9000 ms 8184 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]+L,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 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
24.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 461 ms 2684 KB Output is correct
8 Correct 603 ms 3464 KB Output is correct
9 Correct 2232 ms 7800 KB Output is correct
10 Correct 1600 ms 8008 KB Output is correct
11 Correct 1823 ms 8184 KB Output is correct
12 Correct 6890 ms 7800 KB Output is correct
13 Correct 1575 ms 7800 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 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 461 ms 2684 KB Output is correct
8 Correct 603 ms 3464 KB Output is correct
9 Correct 2232 ms 7800 KB Output is correct
10 Correct 1600 ms 8008 KB Output is correct
11 Correct 1823 ms 8184 KB Output is correct
12 Correct 6890 ms 7800 KB Output is correct
13 Correct 1575 ms 7800 KB Output is correct
14 Correct 2406 ms 3704 KB Output is correct
15 Correct 1077 ms 4484 KB Output is correct
16 Execution timed out 9016 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 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 461 ms 2684 KB Output is correct
8 Correct 603 ms 3464 KB Output is correct
9 Correct 2232 ms 7800 KB Output is correct
10 Correct 1600 ms 8008 KB Output is correct
11 Correct 1823 ms 8184 KB Output is correct
12 Correct 6890 ms 7800 KB Output is correct
13 Correct 1575 ms 7800 KB Output is correct
14 Correct 2406 ms 3704 KB Output is correct
15 Correct 1077 ms 4484 KB Output is correct
16 Execution timed out 9016 ms 7928 KB Time limit exceeded
17 Halted 0 ms 0 KB -