oj.uz

Submission #752232

# Submission time Handle Problem Language Result Execution time Memory
752232 2023-06-02T14:32:39 Z marvinthang Dancing Elephants (IOI11_elephants) C++17
100 / 100
 6776 ms 11236 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 = 1210;

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 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 621 ms 1288 KB Output is correct
8 Correct 642 ms 1448 KB Output is correct
9 Correct 717 ms 2224 KB Output is correct
10 Correct 619 ms 2244 KB Output is correct
11 Correct 639 ms 2260 KB Output is correct
12 Correct 1223 ms 2236 KB Output is correct
13 Correct 625 ms 2260 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 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 621 ms 1288 KB Output is correct
8 Correct 642 ms 1448 KB Output is correct
9 Correct 717 ms 2224 KB Output is correct
10 Correct 619 ms 2244 KB Output is correct
11 Correct 639 ms 2260 KB Output is correct
12 Correct 1223 ms 2236 KB Output is correct
13 Correct 625 ms 2260 KB Output is correct
14 Correct 735 ms 1740 KB Output is correct
15 Correct 880 ms 1760 KB Output is correct
16 Correct 2255 ms 2488 KB Output is correct
17 Correct 2629 ms 3116 KB Output is correct
18 Correct 2458 ms 3012 KB Output is correct
19 Correct 1335 ms 3008 KB Output is correct
20 Correct 2285 ms 3012 KB Output is correct
21 Correct 2187 ms 3000 KB Output is correct
22 Correct 1308 ms 2948 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 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 621 ms 1288 KB Output is correct
8 Correct 642 ms 1448 KB Output is correct
9 Correct 717 ms 2224 KB Output is correct
10 Correct 619 ms 2244 KB Output is correct
11 Correct 639 ms 2260 KB Output is correct
12 Correct 1223 ms 2236 KB Output is correct
13 Correct 625 ms 2260 KB Output is correct
14 Correct 735 ms 1740 KB Output is correct
15 Correct 880 ms 1760 KB Output is correct
16 Correct 2255 ms 2488 KB Output is correct
17 Correct 2629 ms 3116 KB Output is correct
18 Correct 2458 ms 3012 KB Output is correct
19 Correct 1335 ms 3008 KB Output is correct
20 Correct 2285 ms 3012 KB Output is correct
21 Correct 2187 ms 3000 KB Output is correct
22 Correct 1308 ms 2948 KB Output is correct
23 Correct 4516 ms 6016 KB Output is correct
24 Correct 5361 ms 6024 KB Output is correct
25 Correct 3541 ms 6016 KB Output is correct
26 Correct 4254 ms 6028 KB Output is correct
27 Correct 4516 ms 6024 KB Output is correct
28 Correct 2499 ms 5148 KB Output is correct
29 Correct 2386 ms 5148 KB Output is correct
30 Correct 2384 ms 5192 KB Output is correct
31 Correct 2393 ms 5148 KB Output is correct
32 Correct 4890 ms 10492 KB Output is correct
33 Correct 3979 ms 9816 KB Output is correct
34 Correct 4243 ms 10700 KB Output is correct
35 Correct 3767 ms 10996 KB Output is correct
36 Correct 2967 ms 10460 KB Output is correct
37 Correct 5767 ms 11236 KB Output is correct
38 Correct 4915 ms 9700 KB Output is correct
39 Correct 4194 ms 10736 KB Output is correct
40 Correct 4738 ms 9724 KB Output is correct
41 Correct 6776 ms 10556 KB Output is correct
42 Correct 6709 ms 10736 KB Output is correct