Submission #118266

#	Time	Username	Problem	Language	Result	Execution time	Memory
118266		MAMBA	Dancing Elephants (IOI11_elephants)	C++17	50 / 100	9069 ms	4860 KiB

elephants

#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 = 1000;

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());
  for (int i = s[id].size() - 1; ~i; i--) {
    int z = lower_bound(all(s[id]), pii(s[id][i].first + L + 1, -1)) -
            s[id].begin();
    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 (stderr)

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 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3