oj.uz

Submission #118275

# Submission time Handle Problem Language Result Execution time Memory
118275 2019-06-18T14:04:17 Z MAMBA Dancing Elephants (IOI11_elephants) C++17
100 / 100
 7431 ms 15408 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 = 600;

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

void relax(int id) {
  int e = s[id].size() - 1;
  while (e > 0 && s[id][e] < s[id][e - 1]) {
    swap(s[id][e], s[id][e - 1]);
    e--;
  }
  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:101: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 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 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 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 427 ms 1772 KB Output is correct
8 Correct 493 ms 2292 KB Output is correct
9 Correct 512 ms 3488 KB Output is correct
10 Correct 587 ms 3732 KB Output is correct
11 Correct 534 ms 3472 KB Output is correct
12 Correct 1018 ms 3788 KB Output is correct
13 Correct 620 ms 3504 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 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 427 ms 1772 KB Output is correct
8 Correct 493 ms 2292 KB Output is correct
9 Correct 512 ms 3488 KB Output is correct
10 Correct 587 ms 3732 KB Output is correct
11 Correct 534 ms 3472 KB Output is correct
12 Correct 1018 ms 3788 KB Output is correct
13 Correct 620 ms 3504 KB Output is correct
14 Correct 574 ms 2516 KB Output is correct
15 Correct 623 ms 2524 KB Output is correct
16 Correct 1634 ms 3996 KB Output is correct
17 Correct 1819 ms 5376 KB Output is correct
18 Correct 2019 ms 5268 KB Output is correct
19 Correct 1144 ms 5092 KB Output is correct
20 Correct 1852 ms 5368 KB Output is correct
21 Correct 1753 ms 5436 KB Output is correct
22 Correct 1233 ms 5152 KB Output is correct

Subtask #5
3.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 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 427 ms 1772 KB Output is correct
8 Correct 493 ms 2292 KB Output is correct
9 Correct 512 ms 3488 KB Output is correct
10 Correct 587 ms 3732 KB Output is correct
11 Correct 534 ms 3472 KB Output is correct
12 Correct 1018 ms 3788 KB Output is correct
13 Correct 620 ms 3504 KB Output is correct
14 Correct 574 ms 2516 KB Output is correct
15 Correct 623 ms 2524 KB Output is correct
16 Correct 1634 ms 3996 KB Output is correct
17 Correct 1819 ms 5376 KB Output is correct
18 Correct 2019 ms 5268 KB Output is correct
19 Correct 1144 ms 5092 KB Output is correct
20 Correct 1852 ms 5368 KB Output is correct
21 Correct 1753 ms 5436 KB Output is correct
22 Correct 1233 ms 5152 KB Output is correct
23 Correct 3986 ms 10040 KB Output is correct
24 Correct 4509 ms 10096 KB Output is correct
25 Correct 3567 ms 10176 KB Output is correct
26 Correct 5843 ms 10124 KB Output is correct
27 Correct 5219 ms 10076 KB Output is correct
28 Correct 2065 ms 5384 KB Output is correct
29 Correct 2007 ms 5416 KB Output is correct
30 Correct 2102 ms 5496 KB Output is correct
31 Correct 2119 ms 5380 KB Output is correct
32 Correct 5145 ms 14620 KB Output is correct
33 Correct 3953 ms 13928 KB Output is correct
34 Correct 4836 ms 14828 KB Output is correct
35 Correct 3799 ms 15068 KB Output is correct
36 Correct 2690 ms 14640 KB Output is correct
37 Correct 6282 ms 15408 KB Output is correct
38 Correct 5765 ms 13800 KB Output is correct
39 Correct 4762 ms 14916 KB Output is correct
40 Correct 6221 ms 13900 KB Output is correct
41 Correct 7160 ms 14980 KB Output is correct
42 Correct 7431 ms 15144 KB Output is correct