Submission #1007558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007558		c2zi6	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	6164 ms	20688 KiB

elephants

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "elephants.h"

const int BUCKETSIZE = 400;
const int DBUCKETSIZE = 2*BUCKETSIZE + 2;

int l;
int m = 0;
int st[DBUCKETSIZE];
struct BUCKET {
    int n = 0;
    int b[DBUCKETSIZE];
    int cnt[DBUCKETSIZE];
    int mx[DBUCKETSIZE];
    void rem(int x) {
        while (b[n-1] > x) {
            st[m++] = b[--n];
        }
        --n;
        while (m) {
            b[n++] = st[--m];
        }
    }
    void add(int x) {
        while (n && b[n-1] > x) {
            st[m++] = b[--n];
        }
        b[n++] = x;
        while (m) {
            b[n++] = st[--m];
        }
    }
    void recalc() {
        if (n >= 2*BUCKETSIZE + 2) cout << "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA KOD KARMIR KOD KARMIR AAAAAAAAAAAAAAAAAAAAAAAA" << endl;
        reprl(i, n-1, 0) {
            int j = upper_bound(b, b+n, b[i] + l) - b;
            if (j == n) {
                cnt[i] = 1;
                mx[i] = b[i]+l;
            } else {
                cnt[i] = cnt[j]+1;
                mx[i] = mx[j];
            }
        }
    }
    void print() {
        rep(i, n) cout << b[i] << " "; cout << endl;
        /*rep(i, n) cout << cnt[i] << " "; cout << endl;*/
        /*rep(i, n) cout << mx[i] << " "; cout << endl;*/
    }
};

int n;
int a[160000];
int b[160000];
vector<BUCKET> buk;
void recalc() {
    rep(i, n) b[i] = a[i];
    sort(b, b+n);
    buk.clear();
    buk.pb(BUCKET());
    rep(i, n) {
        if (buk.back().n >= BUCKETSIZE) {
            buk.pb(BUCKET());
        }
        buk.back().add(b[i]);
    }
    for (BUCKET& p : buk) p.recalc();
}
void add(int x) {
    for (BUCKET& p : buk) if (p.n) {
        if (x <= p.b[p.n-1]) {
            p.add(x);
            p.recalc();
            return;
        }
    }
    buk.back().add(x);
    buk.back().recalc();
}
void rem(int x) {
    for (BUCKET& p : buk) if (p.n) {
        if (x <= p.b[p.n-1]) {
            p.rem(x);
            p.recalc();
            return;
        }
    }
}

int answer() {
    int ans = 0;
    int R = -2e9;
    for (BUCKET& p : buk) if (p.n) {
        int i = upper_bound(p.b, p.b + p.n, R) - p.b;
        if (i == p.n) continue;
        ans += p.cnt[i];
        R = p.mx[i];
    }
    return ans;
}

void print() {
    rep(i, n) cout << a[i] << " "; cout << endl;
    for (BUCKET& p : buk) {
        cout << "BUCKET: " << endl << "         ";
        p.print();
    }
    cout << "END OF PHASE ----------------------------------------------" << endl;
}

void init(int N, int L, int X[]) {
    n = N;
    l = L;
    rep(i, n) a[i] = X[i];
    recalc();
}

int qr = 0;
int update(int i, int y) {
    if (qr++ % BUCKETSIZE == 0) {
        recalc();
        /*cout << "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx_RECALCULATED_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" << endl;*/
    }
    rem(a[i]);
    a[i] = y;
    add(a[i]);
    /*print();*/
    return answer();
}

Compilation message (stderr)

elephants.cpp: In member function 'void BUCKET::print()':
elephants.cpp:9:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    9 | #define rep(i, n) for (int i = 0; i < int(n); ++i)
      |                   ^~~
elephants.cpp:77:9: note: in expansion of macro 'rep'
   77 |         rep(i, n) cout << b[i] << " "; cout << endl;
      |         ^~~
elephants.cpp:77:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   77 |         rep(i, n) cout << b[i] << " "; cout << endl;
      |                                        ^~~~
elephants.cpp: In function 'void print()':
elephants.cpp:9:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    9 | #define rep(i, n) for (int i = 0; i < int(n); ++i)
      |                   ^~~
elephants.cpp:134:5: note: in expansion of macro 'rep'
  134 |     rep(i, n) cout << a[i] << " "; cout << endl;
      |     ^~~
elephants.cpp:134:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  134 |     rep(i, n) cout << a[i] << " "; cout << endl;
      |                                    ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3