oj.uz

Submission #752276

# Submission time Handle Problem Language Result Execution time Memory
752276 2023-06-02T15:56:14 Z marvinthang Dancing Elephants (IOI11_elephants) C++17
100 / 100
 7765 ms 6548 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 = 800;

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 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

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 340 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 340 KB Output is correct
7 Correct 424 ms 1292 KB Output is correct
8 Correct 443 ms 1336 KB Output is correct
9 Correct 643 ms 2136 KB Output is correct
10 Correct 741 ms 2156 KB Output is correct
11 Correct 705 ms 2156 KB Output is correct
12 Correct 1138 ms 2156 KB Output is correct
13 Correct 797 ms 2156 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 340 KB Output is correct
7 Correct 424 ms 1292 KB Output is correct
8 Correct 443 ms 1336 KB Output is correct
9 Correct 643 ms 2136 KB Output is correct
10 Correct 741 ms 2156 KB Output is correct
11 Correct 705 ms 2156 KB Output is correct
12 Correct 1138 ms 2156 KB Output is correct
13 Correct 797 ms 2156 KB Output is correct
14 Correct 605 ms 1636 KB Output is correct
15 Correct 703 ms 1812 KB Output is correct
16 Correct 1920 ms 2372 KB Output is correct
17 Correct 2077 ms 3008 KB Output is correct
18 Correct 2186 ms 2884 KB Output is correct
19 Correct 1390 ms 2872 KB Output is correct
20 Correct 2033 ms 2868 KB Output is correct
21 Correct 1960 ms 2888 KB Output is correct
22 Correct 1391 ms 2876 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 340 KB Output is correct
7 Correct 424 ms 1292 KB Output is correct
8 Correct 443 ms 1336 KB Output is correct
9 Correct 643 ms 2136 KB Output is correct
10 Correct 741 ms 2156 KB Output is correct
11 Correct 705 ms 2156 KB Output is correct
12 Correct 1138 ms 2156 KB Output is correct
13 Correct 797 ms 2156 KB Output is correct
14 Correct 605 ms 1636 KB Output is correct
15 Correct 703 ms 1812 KB Output is correct
16 Correct 1920 ms 2372 KB Output is correct
17 Correct 2077 ms 3008 KB Output is correct
18 Correct 2186 ms 2884 KB Output is correct
19 Correct 1390 ms 2872 KB Output is correct
20 Correct 2033 ms 2868 KB Output is correct
21 Correct 1960 ms 2888 KB Output is correct
22 Correct 1391 ms 2876 KB Output is correct
23 Correct 4654 ms 5764 KB Output is correct
24 Correct 5110 ms 5760 KB Output is correct
25 Correct 4083 ms 5860 KB Output is correct
26 Correct 4724 ms 5776 KB Output is correct
27 Correct 5333 ms 5776 KB Output is correct
28 Correct 1819 ms 2288 KB Output is correct
29 Correct 1782 ms 2204 KB Output is correct
30 Correct 1834 ms 2204 KB Output is correct
31 Correct 1820 ms 2204 KB Output is correct
32 Correct 5499 ms 5780 KB Output is correct
33 Correct 4698 ms 5896 KB Output is correct
34 Correct 5363 ms 5780 KB Output is correct
35 Correct 4755 ms 5780 KB Output is correct
36 Correct 3672 ms 5868 KB Output is correct
37 Correct 6994 ms 6548 KB Output is correct
38 Correct 6183 ms 5776 KB Output is correct
39 Correct 5392 ms 5780 KB Output is correct
40 Correct 6379 ms 5784 KB Output is correct
41 Correct 7765 ms 5780 KB Output is correct
42 Correct 7606 ms 5772 KB Output is correct