oj.uz

Submission #220505

# Submission time Handle Problem Language Result Execution time Memory
220505 2020-04-08T02:33:34 Z anonymous Dancing Elephants (IOI11_elephants) C++14
26 / 100
 9000 ms 7980 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 && !stray[nxt[at][i]]) {
                                    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:45: 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 5 ms 384 KB Output is correct
2 Correct 9 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 9 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 4 ms 384 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 9 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 4 ms 384 KB Output is correct
7 Correct 465 ms 2808 KB Output is correct
8 Correct 584 ms 3428 KB Output is correct
9 Correct 2372 ms 7948 KB Output is correct
10 Execution timed out 9082 ms 7980 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 9 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 4 ms 384 KB Output is correct
7 Correct 465 ms 2808 KB Output is correct
8 Correct 584 ms 3428 KB Output is correct
9 Correct 2372 ms 7948 KB Output is correct
10 Execution timed out 9082 ms 7980 KB Time limit exceeded
11 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 9 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 4 ms 384 KB Output is correct
7 Correct 465 ms 2808 KB Output is correct
8 Correct 584 ms 3428 KB Output is correct
9 Correct 2372 ms 7948 KB Output is correct
10 Execution timed out 9082 ms 7980 KB Time limit exceeded
11 Halted 0 ms 0 KB -