Submission #394354

#	Time	Username	Problem	Language	Result	Execution time	Memory
394354		MarcoMeijer	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	7280 ms	13056 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;

// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int SQ = 400;

int n, l;
int currentUpdate = 0;
vector<vi> difX;
vector<vii> dp;
vi a, b;

void updateComp(int c) {
    int m = difX[c].size();
    dp[c].clear();
    dp[c].resize(m);

    int ub=m-1;
    REV(lb,0,m) {
        while(difX[c][ub] - difX[c][lb] > l) ub--;
        if(ub == m-1) {
            dp[c][lb] = {1,difX[c][lb]+l};
        } else {
            dp[c][lb] = dp[c][ub+1];
            dp[c][lb].fi++;
        }
    }
}
void updateAll() {
    difX.clear();

    b = a;
    sort(all(b));

    int cc = -1;
    RE(i,n) {
        if(i%SQ == 0) cc++, difX.pb({}), dp.pb({});
        difX[cc].pb(b[i]);
    }
    RE(i,cc+1) updateComp(i);
}
int getCurrent() {
    int m = difX.size();
    int lastX = -1;
    int res = 0;
    RE(i,m) {
        int j = upper_bound(all(difX[i]),lastX) - difX[i].begin();
        if(j == difX[i].size()) continue;
        res += dp[i][j].fi;
        lastX = dp[i][j].se;
    }
    return res;
}

void removeX(int x) {
    int m = difX.size();
    RE(i,m) {
        if(difX[i][0] <= x && x <= difX[i].back()) {
            difX[i].erase(find(all(difX[i]), x));
            updateComp(i);
            break;
        }
    }
}
void insertX(int x) {
    int m = difX.size();
    REV(i,0,m) {
        if(i == 0 || x >= difX[i-1].back()) {
            difX[i].insert(upper_bound(all(difX[i]),x), x);
            updateComp(i);
            break;
        }
    }
}

void init(int N, int L, int X[]) {
    n = N; l = L;
    RE(i,n) a.pb(X[i]);
}

int update(int i, int y) {
    removeX(a[i]);
    a[i] = y;
    insertX(a[i]);

    if(currentUpdate % (SQ-1) == 0) updateAll();
    currentUpdate++;

    return getCurrent();
}

Compilation message (stderr)

elephants.cpp: In function 'int getCurrent()':
elephants.cpp:75:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         if(j == difX[i].size()) continue;
      |            ~~^~~~~~~~~~~~~~~~~

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