Submission #50036

#	Time	Username	Problem	Language	Result	Execution time	Memory
50036		Mamnoon_Siam	Dancing Elephants (IOI11_elephants)	C++17	10 / 100	133 ms	21364 KiB

elephants

#include "elephants.h"
//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

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

#define debug(s) cout<< #s <<" = "<< s <<endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define MEMSET(a,val) memset(a, val, sizeof a)
#define PB push_back
#define endl '\n'

inline int myrand(int l, int r) {
	int ret = rand(); ret <<= 15; ret ^= rand();
	if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
	return ret;
}
template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
    return os<<"(" <<p.first<<", "<<p.second<<")"; }

typedef pair<int, int> ii;
template<typename T> using min_pq =
	priority_queue<T, vector<T>, greater<T> >;

const int maxn = 150005;

const int magic = 50;
int n, L;
vector<int> X;
multiset<int> ms;
int mx_blk, upd_cnt, where[maxn];
vector<int> input[510];

struct bucket {
	vector<int> x, cnt, last;
	bucket() {}
	void prepare() {
		last.back() = x.back() + L - 1, cnt.back() = 1;
		for(int l = x.size() - 2, r = x.size() - 1; l >= 0; l--) {
			while(x[r] > x[l] + L - 1) r--;
			if(r == x.size() - 1) cnt[l] = 1, last[l] = x[l] + L - 1;
			else cnt[l] = cnt[r + 1] + 1, last[l] = last[r + 1];
		}
	}
	void assign(vector<int> &v) { x = v;
		cnt.resize(v.size()), last.resize(v.size());
		prepare();
	}
	void insert(int _x) {
		x.insert(lower_bound(all(x), _x), _x);
		cnt.push_back(0), last.push_back(0);
		prepare();
	}
	void erase(int _x) {
		assert(x.size());
		x.erase(find(all(x), _x));
		last.pop_back(), cnt.pop_back();
		prepare();
	}
	ii cnt_last(int _x) {
		int it = upper_bound(all(x), _x) - x.begin();
		if(it == x.size()) { return ii(0, _x); }
		return ii(cnt[it], last[it]);
	}
};

bucket chunk[510];

void refresh() {
	upd_cnt = 0;
	X.clear();
	for(int b : ms) X.push_back(b);
	for(int i = 0; i <= mx_blk; i++) input[i].clear();
	for(int i = 0; i < X.size(); i++) {
		input[i / magic].push_back(X[i]);
		where[i] = i / magic;
	}
	for(int i = 0; i <= mx_blk; i++) {
		chunk[i].assign(input[i]);
	}
}

void init(int _n, int _L, int _X[]) {
	n = _n, L = _L; L++;
	X.resize(n);
	for(int i = 0; i < n; i++) {
		X[i] = _X[i];
		ms.insert(X[i]);
	}
	mx_blk = (X.size() - 1) / magic;
	refresh();

}

int update(int i, int y) {
	ms.erase(ms.find(X[i]));
	chunk[where[i]].erase(X[i]);
	for(int j = 0; j <= mx_blk; j++) {
		if(chunk[j].x.size() == 0) continue;
		if(y <= chunk[j].x.back()) {
			chunk[j].insert(y);
			where[i] = j;
			break;
		}
		if(j == mx_blk) {
			chunk[j].insert(y);
			where[i] = j;
		}
	}
	ms.insert(y);
	X[i] = y;

	int ret = 0, now = -1;
	for(int i = 0; i <= mx_blk; i++) {
		ii cur = chunk[i].cnt_last(now);
		ret += cur.first;
		now = cur.second;
	}

	upd_cnt++;
	if(upd_cnt == magic) {
		refresh();
	}
	return ret;
}

Compilation message (stderr)

elephants.cpp: In function 'int myrand(int, int)':
elephants.cpp:17:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
  ^~
elephants.cpp:17:26: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
                          ^~~
elephants.cpp: In member function 'void bucket::prepare()':
elephants.cpp:44:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(r == x.size() - 1) cnt[l] = 1, last[l] = x[l] + L - 1;
       ~~^~~~~~~~~~~~~~~
elephants.cpp: In member function 'ii bucket::cnt_last(int)':
elephants.cpp:65:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(it == x.size()) { return ii(0, _x); }
      ~~~^~~~~~~~~~~
elephants.cpp: In function 'void refresh()':
elephants.cpp:77:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < X.size(); i++) {
                 ~~^~~~~~~~~~

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