oj.uz

Submission #118271

# Submission time Handle Problem Language Result Execution time Memory
118271 2019-06-18T14:00:23 Z MAMBA Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 14264 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 = 500;

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 3 ms 304 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 3 ms 304 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2683 ms 1772 KB Output is correct
8 Correct 2710 ms 2156 KB Output is correct
9 Correct 1496 ms 3292 KB Output is correct
10 Correct 1139 ms 3232 KB Output is correct
11 Correct 1121 ms 3224 KB Output is correct
12 Correct 2120 ms 3416 KB Output is correct
13 Correct 1150 ms 3204 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 3 ms 304 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2683 ms 1772 KB Output is correct
8 Correct 2710 ms 2156 KB Output is correct
9 Correct 1496 ms 3292 KB Output is correct
10 Correct 1139 ms 3232 KB Output is correct
11 Correct 1121 ms 3224 KB Output is correct
12 Correct 2120 ms 3416 KB Output is correct
13 Correct 1150 ms 3204 KB Output is correct
14 Correct 2070 ms 2440 KB Output is correct
15 Correct 1917 ms 2488 KB Output is correct
16 Correct 3126 ms 3472 KB Output is correct
17 Correct 3361 ms 4716 KB Output is correct
18 Correct 3502 ms 4772 KB Output is correct
19 Correct 4385 ms 4612 KB Output is correct
20 Correct 3347 ms 4824 KB Output is correct
21 Correct 3417 ms 4896 KB Output is correct
22 Correct 2041 ms 4636 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 3 ms 304 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2683 ms 1772 KB Output is correct
8 Correct 2710 ms 2156 KB Output is correct
9 Correct 1496 ms 3292 KB Output is correct
10 Correct 1139 ms 3232 KB Output is correct
11 Correct 1121 ms 3224 KB Output is correct
12 Correct 2120 ms 3416 KB Output is correct
13 Correct 1150 ms 3204 KB Output is correct
14 Correct 2070 ms 2440 KB Output is correct
15 Correct 1917 ms 2488 KB Output is correct
16 Correct 3126 ms 3472 KB Output is correct
17 Correct 3361 ms 4716 KB Output is correct
18 Correct 3502 ms 4772 KB Output is correct
19 Correct 4385 ms 4612 KB Output is correct
20 Correct 3347 ms 4824 KB Output is correct
21 Correct 3417 ms 4896 KB Output is correct
22 Correct 2041 ms 4636 KB Output is correct
23 Correct 7843 ms 9172 KB Output is correct
24 Correct 8605 ms 9312 KB Output is correct
25 Correct 7139 ms 14264 KB Output is correct
26 Correct 7833 ms 14220 KB Output is correct
27 Execution timed out 9042 ms 14148 KB Time limit exceeded
28 Halted 0 ms 0 KB -