oj.uz

Submission #752228

# Submission time Handle Problem Language Result Execution time Memory
752228 2023-06-02T14:26:28 Z marvinthang Dancing Elephants (IOI11_elephants) C++17
97 / 100
 2484 ms 10828 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;
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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 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 1 ms 340 KB Output is correct
3 Correct 1 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 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 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 298 ms 2180 KB Output is correct
8 Correct 362 ms 2460 KB Output is correct
9 Correct 740 ms 3712 KB Output is correct
10 Correct 1002 ms 3508 KB Output is correct
11 Correct 957 ms 3444 KB Output is correct
12 Correct 1285 ms 3708 KB Output is correct
13 Correct 1113 ms 3300 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 1 ms 340 KB Output is correct
3 Correct 1 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 298 ms 2180 KB Output is correct
8 Correct 362 ms 2460 KB Output is correct
9 Correct 740 ms 3712 KB Output is correct
10 Correct 1002 ms 3508 KB Output is correct
11 Correct 957 ms 3444 KB Output is correct
12 Correct 1285 ms 3708 KB Output is correct
13 Correct 1113 ms 3300 KB Output is correct
14 Correct 576 ms 3168 KB Output is correct
15 Correct 637 ms 3148 KB Output is correct
16 Correct 1921 ms 4208 KB Output is correct
17 Correct 2352 ms 4940 KB Output is correct
18 Correct 2484 ms 4868 KB Output is correct
19 Correct 1939 ms 5088 KB Output is correct
20 Correct 2356 ms 5056 KB Output is correct
21 Correct 2388 ms 4924 KB Output is correct
22 Correct 2147 ms 4508 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 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 298 ms 2180 KB Output is correct
8 Correct 362 ms 2460 KB Output is correct
9 Correct 740 ms 3712 KB Output is correct
10 Correct 1002 ms 3508 KB Output is correct
11 Correct 957 ms 3444 KB Output is correct
12 Correct 1285 ms 3708 KB Output is correct
13 Correct 1113 ms 3300 KB Output is correct
14 Correct 576 ms 3168 KB Output is correct
15 Correct 637 ms 3148 KB Output is correct
16 Correct 1921 ms 4208 KB Output is correct
17 Correct 2352 ms 4940 KB Output is correct
18 Correct 2484 ms 4868 KB Output is correct
19 Correct 1939 ms 5088 KB Output is correct
20 Correct 2356 ms 5056 KB Output is correct
21 Correct 2388 ms 4924 KB Output is correct
22 Correct 2147 ms 4508 KB Output is correct
23 Incorrect 75 ms 10828 KB Output isn't correct
24 Halted 0 ms 0 KB -