oj.uz

Submission #220500

# Submission time Handle Problem Language Result Execution time Memory
220500 2020-04-08T02:27:17 Z anonymous Dancing Elephants (IOI11_elephants) C++14
26 / 100
 9000 ms 8056 KB 
        #include "elephants.h"
        #include <iostream>
        #include <set>
        #include <utility>
        #include <cassert>
        #define MAXN 50005
        #define K 225
        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]+L,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]+L,MAXN})).first < (*S.upper_bound({Pos[at]+L,MAXN})).first) {
                            CritPos = (*G.upper_bound({Pos[at]+L,MAXN})).first;
                        } else {
                            CritPos = (*S.upper_bound({Pos[at]+L,MAXN})).first;
                        }
                        for (int i = 19; i >= 0; i--) {
                            if (Prev[nxt[at][i]] < CritPos) {
                                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:41: 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 4 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 4 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 4 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 448 ms 2808 KB Output is correct
8 Correct 595 ms 3448 KB Output is correct
9 Correct 2407 ms 7884 KB Output is correct
10 Execution timed out 9048 ms 8056 KB Time limit exceeded
11 Halted 0 ms 0 KB -

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 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 448 ms 2808 KB Output is correct
8 Correct 595 ms 3448 KB Output is correct
9 Correct 2407 ms 7884 KB Output is correct
10 Execution timed out 9048 ms 8056 KB Time limit exceeded
11 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 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 448 ms 2808 KB Output is correct
8 Correct 595 ms 3448 KB Output is correct
9 Correct 2407 ms 7884 KB Output is correct
10 Execution timed out 9048 ms 8056 KB Time limit exceeded
11 Halted 0 ms 0 KB -