oj.uz

Submission #220487

# Submission time Handle Problem Language Result Execution time Memory
220487 2020-04-08T02:04:18 Z anonymous Dancing Elephants (IOI11_elephants) C++14
26 / 100
 9000 ms 3576 KB 
    #include "elephants.h"
    #include <iostream>
    #include <set>
    #include <utility>
    #include <cassert>
    #define MAXN 150005
    #define K 1
    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({2e9 + 5, N}); //dummy
      Pos[N] = 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;
        }
        makeJump();
      }
      int at = (*E.begin()).second, Ans = 0;
      while (at != N) {
           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}) < *S.upper_bound({Pos[at] + L,MAXN})) {
                        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 (Pos[nxt[at][i]] < CritPos) {
                            at = nxt[at][i];
                            Ans += (1<<i);
                        }
                    }
                    Ans+=1;
                    at = Next(Pos[at]);
               }
           }
      }
      return(Ans);
    }

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 5 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
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 Execution timed out 9044 ms 3576 KB Time limit exceeded
8 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 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 Execution timed out 9044 ms 3576 KB Time limit exceeded
8 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 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 Execution timed out 9044 ms 3576 KB Time limit exceeded
8 Halted 0 ms 0 KB -