oj.uz

답안 #752229

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
752229 2023-06-02T14:28:09 Z marvinthang 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
97 / 100
 9000 ms 10880 KB 
/*************************************
*    author: marvinthang             *
*    created: 02.06.2023 20:52:17    *
*************************************/

#include "elephants.h"
#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

// end of template

const int MAX = 1.5e5 + 5;
const int BUCKET_SIZE = 380;

int N, L, X[MAX], cnt, numBucket;
vector <int> buckets[MAX / BUCKET_SIZE + 23];
pair <int, int> nxt[MAX];

bool cmp(int x, int y) {
    return make_pair(X[x], x) < make_pair(X[y], y);
}

void build_bucket(int b) {
    int n = buckets[b].size();
    int j = n;
    REPD(x, n) {
        int i = buckets[b][x];
        while (X[buckets[b][j - 1]] > X[i] + L) --j;
        if (j == n) nxt[i] = make_pair(X[i] + L, 1);
        else nxt[i] = make_pair(nxt[buckets[b][j]].fi, nxt[buckets[b][j]].se + 1);
    }
}

void bucket_add(int b, int i) {
    buckets[b].insert(upper_bound(ALL(buckets[b]), i, cmp), i);
    build_bucket(b);
}

void bucket_erase(int b, int i) {
    buckets[b].erase(find(ALL(buckets[b]), i));
    build_bucket(b);
}

void build(void) {
    vector <int> pos(N);
    iota(ALL(pos), 0);
    sort(ALL(pos), cmp);
    REP(i, numBucket) buckets[i].clear();
    REP(i, N) buckets[i / BUCKET_SIZE].push_back(pos[i]);
    REP(i, numBucket) build_bucket(i);
}

void init(int n, int l, int x[]) {
    N = n; L = l;
    numBucket = (N - 1) / BUCKET_SIZE + 1;
    REP(i, N) X[i] = x[i];
    build();
}

int get_answer(void) {
    int res = 0;
    X[N] = -1;
    REP(b, numBucket) if (!buckets[b].empty()) {
        int p = upper_bound(ALL(buckets[b]), N, cmp) - buckets[b].begin();
        if (p == buckets[b].size()) continue;
        p = buckets[b][p];
        res += nxt[p].se;
        X[N] = nxt[p].fi;
    }
    return res;
}

int update(int i, int y) {
    REP(b, numBucket) if (!buckets[b].empty() && !cmp(buckets[b].back(), i)) {
        bucket_erase(b, i);
        break;
    }
    X[i] = y;
    REP(b, numBucket) if (b == numBucket - 1 || (!buckets[b].empty() && !cmp(buckets[b].back(), i))) {
        bucket_add(b, i);
        break;
    }
    if (++cnt == BUCKET_SIZE) {
        build();
        cnt = 0;
    }
    return get_answer();
}

#ifdef LOCAL
#include "elephants.h"
#include <stdio.h>
#include <stdlib.h>

#define MAX_N 1000000
#define MAX_M 1000000

static int n,l,m;
static int x[MAX_N];
static int ii[MAX_M];
static int yy[MAX_M];
static int sol[MAX_M];

inline 
void my_assert(int e) {if (!e) abort();}

void read_input()
{
  int i;
  my_assert(3==scanf("%d %d %d",&n,&l,&m));
  for(i=0; i<n; i++)
    my_assert(1==scanf("%d",&x[i]));
  for(i=0; i<m; i++)
    my_assert(3==scanf("%d %d %d",&ii[i],&yy[i],&sol[i]));
}

int main()
{
    file("elephants");
  int i, ans;

  read_input();
  init(n,l,x);
  for(i=0; i<m; i++) {
    ans = update(ii[i],yy[i]);
    if(ans==sol[i])continue;
      printf("Incorrect.  In %d-th move, answered %d (%d expected).\n",
       i+1, ans, sol[i]);
    return 0;
  }
  printf("Correct.\n");
  return 0;
}
#endif

Compilation message

elephants.cpp: In function 'int get_answer()':
elephants.cpp:99:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         if (p == buckets[b].size()) continue;
      |             ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 303 ms 1236 KB Output is correct
8 Correct 366 ms 1568 KB Output is correct
9 Correct 695 ms 2180 KB Output is correct
10 Correct 974 ms 2172 KB Output is correct
11 Correct 957 ms 2168 KB Output is correct
12 Correct 1272 ms 2172 KB Output is correct
13 Correct 1079 ms 2172 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 303 ms 1236 KB Output is correct
8 Correct 366 ms 1568 KB Output is correct
9 Correct 695 ms 2180 KB Output is correct
10 Correct 974 ms 2172 KB Output is correct
11 Correct 957 ms 2168 KB Output is correct
12 Correct 1272 ms 2172 KB Output is correct
13 Correct 1079 ms 2172 KB Output is correct
14 Correct 576 ms 1656 KB Output is correct
15 Correct 636 ms 1732 KB Output is correct
16 Correct 1915 ms 2392 KB Output is correct
17 Correct 2344 ms 2904 KB Output is correct
18 Correct 2524 ms 2920 KB Output is correct
19 Correct 1950 ms 2896 KB Output is correct
20 Correct 2372 ms 3028 KB Output is correct
21 Correct 2386 ms 3028 KB Output is correct
22 Correct 2078 ms 2896 KB Output is correct

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 303 ms 1236 KB Output is correct
8 Correct 366 ms 1568 KB Output is correct
9 Correct 695 ms 2180 KB Output is correct
10 Correct 974 ms 2172 KB Output is correct
11 Correct 957 ms 2168 KB Output is correct
12 Correct 1272 ms 2172 KB Output is correct
13 Correct 1079 ms 2172 KB Output is correct
14 Correct 576 ms 1656 KB Output is correct
15 Correct 636 ms 1732 KB Output is correct
16 Correct 1915 ms 2392 KB Output is correct
17 Correct 2344 ms 2904 KB Output is correct
18 Correct 2524 ms 2920 KB Output is correct
19 Correct 1950 ms 2896 KB Output is correct
20 Correct 2372 ms 3028 KB Output is correct
21 Correct 2386 ms 3028 KB Output is correct
22 Correct 2078 ms 2896 KB Output is correct
23 Correct 6941 ms 5824 KB Output is correct
24 Correct 7236 ms 10860 KB Output is correct
25 Correct 6384 ms 10856 KB Output is correct
26 Correct 8383 ms 10880 KB Output is correct
27 Execution timed out 9047 ms 10700 KB Time limit exceeded
28 Halted 0 ms 0 KB -