oj.uz

Submission #220516

# Submission time Handle Problem Language Result Execution time Memory
220516 2020-04-08T03:06:10 Z anonymous Dancing Elephants (IOI11_elephants) C++14
50 / 100
 9000 ms 7960 KB 
  #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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 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 5 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 5 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 424 ms 2664 KB Output is correct
8 Correct 533 ms 3448 KB Output is correct
9 Correct 2023 ms 7712 KB Output is correct
10 Correct 1233 ms 7800 KB Output is correct
11 Correct 1557 ms 7960 KB Output is correct
12 Correct 7359 ms 7800 KB Output is correct
13 Correct 1222 ms 7808 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 5 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 424 ms 2664 KB Output is correct
8 Correct 533 ms 3448 KB Output is correct
9 Correct 2023 ms 7712 KB Output is correct
10 Correct 1233 ms 7800 KB Output is correct
11 Correct 1557 ms 7960 KB Output is correct
12 Correct 7359 ms 7800 KB Output is correct
13 Correct 1222 ms 7808 KB Output is correct
14 Correct 2559 ms 3704 KB Output is correct
15 Correct 919 ms 4480 KB Output is correct
16 Execution timed out 9048 ms 7836 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 5 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 424 ms 2664 KB Output is correct
8 Correct 533 ms 3448 KB Output is correct
9 Correct 2023 ms 7712 KB Output is correct
10 Correct 1233 ms 7800 KB Output is correct
11 Correct 1557 ms 7960 KB Output is correct
12 Correct 7359 ms 7800 KB Output is correct
13 Correct 1222 ms 7808 KB Output is correct
14 Correct 2559 ms 3704 KB Output is correct
15 Correct 919 ms 4480 KB Output is correct
16 Execution timed out 9048 ms 7836 KB Time limit exceeded
17 Halted 0 ms 0 KB -