oj.uz

Submission #220512

# Submission time Handle Problem Language Result Execution time Memory
220512 2020-04-08T02:59:19 Z anonymous Dancing Elephants (IOI11_elephants) C++14
50 / 100
 9000 ms 7940 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 {
                           if (G.upper_bound({Pos[at],MAXN}) == G.end() && S.upper_bound({Pos[at]+L,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]+L,MAXN}) == S.end() ||  (G.upper_bound({Pos[at], MAXN}) != G.end() && (*G.upper_bound({Pos[at], MAXN})).first < (*S.upper_bound({Pos[at]+L,MAXN})).first)) {
                                    CritPos = (*G.upper_bound({Pos[at],MAXN})).first;
                                } else {
                                    CritPos = (*S.upper_bound({Pos[at]+L,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]);
                           }
                       }
                  }
                  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 5 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 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 5 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 467 ms 2680 KB Output is correct
8 Correct 606 ms 3360 KB Output is correct
9 Correct 2481 ms 7776 KB Output is correct
10 Correct 1578 ms 7672 KB Output is correct
11 Correct 1864 ms 7800 KB Output is correct
12 Correct 8073 ms 7752 KB Output is correct
13 Correct 1534 ms 7940 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 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 467 ms 2680 KB Output is correct
8 Correct 606 ms 3360 KB Output is correct
9 Correct 2481 ms 7776 KB Output is correct
10 Correct 1578 ms 7672 KB Output is correct
11 Correct 1864 ms 7800 KB Output is correct
12 Correct 8073 ms 7752 KB Output is correct
13 Correct 1534 ms 7940 KB Output is correct
14 Correct 2841 ms 3588 KB Output is correct
15 Correct 1171 ms 4600 KB Output is correct
16 Execution timed out 9066 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 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 467 ms 2680 KB Output is correct
8 Correct 606 ms 3360 KB Output is correct
9 Correct 2481 ms 7776 KB Output is correct
10 Correct 1578 ms 7672 KB Output is correct
11 Correct 1864 ms 7800 KB Output is correct
12 Correct 8073 ms 7752 KB Output is correct
13 Correct 1534 ms 7940 KB Output is correct
14 Correct 2841 ms 3588 KB Output is correct
15 Correct 1171 ms 4600 KB Output is correct
16 Execution timed out 9066 ms 7928 KB Time limit exceeded
17 Halted 0 ms 0 KB -