oj.uz

Submission #118269

# Submission time Handle Problem Language Result Execution time Memory
118269 2019-06-18T13:59:34 Z MAMBA Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 9056 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 = 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());
  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 4620 ms 1844 KB Output is correct
8 Correct 4599 ms 2168 KB Output is correct
9 Correct 2741 ms 3304 KB Output is correct
10 Correct 1625 ms 3200 KB Output is correct
11 Correct 1791 ms 3288 KB Output is correct
12 Correct 3605 ms 3484 KB Output is correct
13 Correct 1657 ms 3296 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 4620 ms 1844 KB Output is correct
8 Correct 4599 ms 2168 KB Output is correct
9 Correct 2741 ms 3304 KB Output is correct
10 Correct 1625 ms 3200 KB Output is correct
11 Correct 1791 ms 3288 KB Output is correct
12 Correct 3605 ms 3484 KB Output is correct
13 Correct 1657 ms 3296 KB Output is correct
14 Correct 3733 ms 2280 KB Output is correct
15 Correct 3987 ms 2384 KB Output is correct
16 Correct 5299 ms 3736 KB Output is correct
17 Correct 5445 ms 4852 KB Output is correct
18 Correct 5420 ms 5064 KB Output is correct
19 Correct 8000 ms 4672 KB Output is correct
20 Correct 5139 ms 4912 KB Output is correct
21 Correct 5060 ms 4900 KB Output is correct
22 Correct 2520 ms 4596 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 4620 ms 1844 KB Output is correct
8 Correct 4599 ms 2168 KB Output is correct
9 Correct 2741 ms 3304 KB Output is correct
10 Correct 1625 ms 3200 KB Output is correct
11 Correct 1791 ms 3288 KB Output is correct
12 Correct 3605 ms 3484 KB Output is correct
13 Correct 1657 ms 3296 KB Output is correct
14 Correct 3733 ms 2280 KB Output is correct
15 Correct 3987 ms 2384 KB Output is correct
16 Correct 5299 ms 3736 KB Output is correct
17 Correct 5445 ms 4852 KB Output is correct
18 Correct 5420 ms 5064 KB Output is correct
19 Correct 8000 ms 4672 KB Output is correct
20 Correct 5139 ms 4912 KB Output is correct
21 Correct 5060 ms 4900 KB Output is correct
22 Correct 2520 ms 4596 KB Output is correct
23 Execution timed out 9096 ms 9056 KB Time limit exceeded
24 Halted 0 ms 0 KB -