oj.uz

답안 #118267

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
118267 2019-06-18T13:56:23 Z MAMBA 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
97 / 100
 9000 ms 14592 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());
  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

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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 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 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3259 ms 1900 KB Output is correct
8 Correct 3237 ms 2188 KB Output is correct
9 Correct 3049 ms 3604 KB Output is correct
10 Correct 2826 ms 3384 KB Output is correct
11 Correct 2694 ms 3528 KB Output is correct
12 Correct 3683 ms 3644 KB Output is correct
13 Correct 2760 ms 3528 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 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 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3259 ms 1900 KB Output is correct
8 Correct 3237 ms 2188 KB Output is correct
9 Correct 3049 ms 3604 KB Output is correct
10 Correct 2826 ms 3384 KB Output is correct
11 Correct 2694 ms 3528 KB Output is correct
12 Correct 3683 ms 3644 KB Output is correct
13 Correct 2760 ms 3528 KB Output is correct
14 Correct 3091 ms 2532 KB Output is correct
15 Correct 3830 ms 2544 KB Output is correct
16 Correct 5272 ms 5708 KB Output is correct
17 Correct 5853 ms 7092 KB Output is correct
18 Correct 5752 ms 7128 KB Output is correct
19 Correct 6781 ms 7076 KB Output is correct
20 Correct 5996 ms 7092 KB Output is correct
21 Correct 5930 ms 7100 KB Output is correct
22 Correct 4701 ms 6564 KB Output is correct

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 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 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3259 ms 1900 KB Output is correct
8 Correct 3237 ms 2188 KB Output is correct
9 Correct 3049 ms 3604 KB Output is correct
10 Correct 2826 ms 3384 KB Output is correct
11 Correct 2694 ms 3528 KB Output is correct
12 Correct 3683 ms 3644 KB Output is correct
13 Correct 2760 ms 3528 KB Output is correct
14 Correct 3091 ms 2532 KB Output is correct
15 Correct 3830 ms 2544 KB Output is correct
16 Correct 5272 ms 5708 KB Output is correct
17 Correct 5853 ms 7092 KB Output is correct
18 Correct 5752 ms 7128 KB Output is correct
19 Correct 6781 ms 7076 KB Output is correct
20 Correct 5996 ms 7092 KB Output is correct
21 Correct 5930 ms 7100 KB Output is correct
22 Correct 4701 ms 6564 KB Output is correct
23 Execution timed out 9017 ms 14592 KB Time limit exceeded
24 Halted 0 ms 0 KB -