oj.uz

Submission #118273

# Submission time Handle Problem Language Result Execution time Memory
118273 2019-06-18T14:00:47 Z MAMBA Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 9688 KB 
#include "elephants.h"
#include <bits/stdc++.h>

using namespace std;

inline void read() {}
template <class S>
inline void read(S &arg) {
  cin >> arg;
}
template <class S>
inline void readA(S Lptr, S Rptr) {
  while (Lptr != Rptr) {
    read(*Lptr);
    Lptr++;
  }
}
template <class S, class... T>
inline void read(S &arg, T &... rest) {
  read(arg);
  read(rest...);
}

inline void write() {}
template <class S>
inline void write(S arg) {
  cout << arg;
}
template <class S>
inline void writeA(S Lptr, S Rptr, char C_ = ' ') {
  if (Lptr != Rptr) {
    write(*Lptr);
    Lptr++;
  }
  while (Lptr != Rptr) {
    write(C_);
    write(*Lptr);
    Lptr++;
  }
}
template <class S, class... T>
inline void write(S arg, T... rest) {
  write(arg);
  write(' ');
  write(rest...);
}

#define rep(i, j, k) for (int i = j; i < (int)k; i++)
#define pb push_back
#define mt make_tuple
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

template <class T, class S>
inline bool smin(T &a, S b) {
  return (T)b < a ? a = b, 1 : 0;
}
template <class T, class S>
inline bool smax(T &a, S b) {
  return a < (T)b ? a = b, 1 : 0;
}

constexpr int MOD = 1e9 + 7;
constexpr int N = 150 * 1000 + 10;

template <typename T>
inline T mod(T &v) {
  return v = (v % MOD + MOD) % MOD;
}
template <typename S, typename T>
inline S add(S &l, T r) {
  return mod(l += r);
}

ll po(ll v, ll u) {
  return u ? po(v * v % MOD, u >> 1) * (u & 1 ? v : 1) % MOD : 1;
}

const int sq = 400;

int n, L, pos[N];
vector<pii> s[N / sq + 10];
vector<pii> dp[N / sq + 10];

void relax(int id) {
  sort(all(s[id]));
  dp[id] = vector<pii>(s[id].size());
  int z = s[id].size();
  for (int i = s[id].size() - 1; ~i; i--) {
    while (s[id][z - 1].first > s[id][i].first + L) z--;
    dp[id][i].first = 1;
    dp[id][i].second = s[id][i].first + L;
    if (z != s[id].size()) {
      dp[id][i].first += dp[id][z].first;
      dp[id][i].second = dp[id][z].second;
    }
  }
}

void init(int n_, int L_, int X[]) {
  n = n_;
  L = L_;
  memcpy(pos, X, 4 * n_);
  vector<pii> vec;
  rep(i, 0, n) vec.pb({X[i], i});
  sort(all(vec));
  for (int i = 0; i * sq < n; i++) {
    int l = i * sq;
    int r = min(n, l + sq);
    s[i].clear();
    rep(j, l, r) s[i].pb(vec[j]);
    relax(i);
  }
}

int Nu;
int update(int me, int y) {
  if (n == 1) return 1;
  Nu++;
  if (Nu % sq == 0) init(n, L, pos);

  bool flag = false;
  for (int i = 0; !flag; i++)
    if (s[i].size() && pii(pos[me], me) <= s[i].back()) {
      for (int j = 0; !flag; j++)
        if (s[i][j] == pii(pos[me], me)) {
          s[i].erase(s[i].begin() + j);
          flag = true;
        }
      relax(i);
    }

  pos[me] = y;
  for (int i = 0;; i++)
    if ((i + 1) * sq >= n || (s[i].size() && pii(pos[me], me) <= s[i].back())) {
      s[i].pb(pii(pos[me], me));
      relax(i);
      break;
    }
  int res = 0;
  int last = -1;
  for (int i = 0; i * sq < n; i++) {
    if (s[i].empty() || s[i].back().first <= last) continue;
    int id = lower_bound(all(s[i]), pii(last + 1, -1)) - s[i].begin();
    res += dp[i][id].first;
    last = dp[i][id].second;
  }
  return res;
}

Compilation message

elephants.cpp: In function 'void relax(int)':
elephants.cpp:97:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (z != s[id].size()) {
         ~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1650 ms 1816 KB Output is correct
8 Correct 1601 ms 2108 KB Output is correct
9 Correct 1409 ms 3416 KB Output is correct
10 Correct 1105 ms 3404 KB Output is correct
11 Correct 1135 ms 3444 KB Output is correct
12 Correct 1917 ms 3456 KB Output is correct
13 Correct 1135 ms 3336 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1650 ms 1816 KB Output is correct
8 Correct 1601 ms 2108 KB Output is correct
9 Correct 1409 ms 3416 KB Output is correct
10 Correct 1105 ms 3404 KB Output is correct
11 Correct 1135 ms 3444 KB Output is correct
12 Correct 1917 ms 3456 KB Output is correct
13 Correct 1135 ms 3336 KB Output is correct
14 Correct 1616 ms 2316 KB Output is correct
15 Correct 1682 ms 2496 KB Output is correct
16 Correct 2995 ms 3656 KB Output is correct
17 Correct 3311 ms 5012 KB Output is correct
18 Correct 3413 ms 4976 KB Output is correct
19 Correct 3789 ms 4808 KB Output is correct
20 Correct 3202 ms 5032 KB Output is correct
21 Correct 3310 ms 5012 KB Output is correct
22 Correct 2001 ms 4808 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1650 ms 1816 KB Output is correct
8 Correct 1601 ms 2108 KB Output is correct
9 Correct 1409 ms 3416 KB Output is correct
10 Correct 1105 ms 3404 KB Output is correct
11 Correct 1135 ms 3444 KB Output is correct
12 Correct 1917 ms 3456 KB Output is correct
13 Correct 1135 ms 3336 KB Output is correct
14 Correct 1616 ms 2316 KB Output is correct
15 Correct 1682 ms 2496 KB Output is correct
16 Correct 2995 ms 3656 KB Output is correct
17 Correct 3311 ms 5012 KB Output is correct
18 Correct 3413 ms 4976 KB Output is correct
19 Correct 3789 ms 4808 KB Output is correct
20 Correct 3202 ms 5032 KB Output is correct
21 Correct 3310 ms 5012 KB Output is correct
22 Correct 2001 ms 4808 KB Output is correct
23 Correct 7783 ms 9504 KB Output is correct
24 Correct 8803 ms 9592 KB Output is correct
25 Correct 7412 ms 9680 KB Output is correct
26 Correct 8546 ms 9688 KB Output is correct
27 Execution timed out 9023 ms 9588 KB Time limit exceeded
28 Halted 0 ms 0 KB -