제출 #50039

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
50039		Mamnoon_Siam	코끼리 (Dancing Elephants) (IOI11_elephants)	C++17	10 / 100	1076 ms	23652 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, to;
multiset<int> ms;
int mx_blk, upd_cnt, where[maxn];
vector<int> input[510];

struct bucket {
	vector<int> x, cnt, last;
	bucket() {}
	void prepare() {
		if(x.size() == 0) return;
		//cout << "in" << endl;
		assert(last.size());
		assert(x.size());
		assert(cnt.size());
		last[last.size()-1] = x[x.size()-1] + L - 1, cnt[cnt.size()-1] = 1;
		for(int l = x.size() - 2, r = x.size() - 1; l >= 0; l--) {
			while(x[r] > x[l] + L - 1) r--, assert(r >= 0);
			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);
		//cout << "another voila" << endl;
		//debug(x.size());
		//for(int b : x) cout << b << ' '; cout << endl;
		//cnt.push_back(0);
		//last.push_back(0);
		cnt.resize(x.size());
		last.resize(x.size());
		//cout << "hehe" << endl;
		prepare();
	}
	void erase(int _x) {
		assert(x.size());
		auto it = find(all(x), _x);
		assert(it != x.end());
		x.erase(it);
		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]);
	}
	void print() {
		for(int b : x) cout << b << ' '; cout << endl;
		for(int b : cnt) cout << b << ' '; cout << endl;
		for(int b : last) cout << b << ' '; cout << endl;
	}
};

bucket chunk[510];

void refresh() {
	//cout << "refreshing" << endl;
	upd_cnt = 0;
	vector<int> temp(X.size());
	for(int i = 0; i < X.size(); i++) temp[i] = X[to[i]];
	for(int i = 0; i < X.size(); i++) to[i] = i;
	sort(all(to), [&temp](int p, int q){ return temp[p] < temp[q]; });
	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]);
	}
	to.resize(n);
	for(int i = 0; i < n; i++) to[i] = i;
	mx_blk = (X.size() - 1) / magic;
	refresh();

}

int update(int i, int y) {
	//cout << "Starting ........ " << endl;

	ms.erase(ms.find(X[i]));

	//cout << "again" << endl;

	//debug(where[i]);

	chunk[where[i]].erase(X[i]);

	//cout << "crossed" << endl;

	for(int j = 0; j <= mx_blk; j++) {
		//cout << "pre = " << j << endl;
		//debug(chunk[j].x.size());
		if(chunk[j].x.size() == 0) {
			//cout << "going to hell" << endl;
			goto hell;
		}
		//cout << "mid" << endl;
		if(y <= chunk[j].x.back()) {
			//cout << "yahoooo" << endl;
			//debug(chunk[j].x.size());
			chunk[j].insert(y);
			//cout << "found" << endl;
			where[i] = j;
			//cout << "been here" << endl;
			break;
		}
		hell : ;
		//cout << "J = " << j << endl;
		if(j == mx_blk) {
			//cout << "here" << endl;
			chunk[j].insert(y);
			where[i] = j;
		}
	}

	//cout << "voila" << endl;
	ms.insert(y);
	X[i] = y;

	//cout << endl << "New Update" << endl;

	if(false) {
		for(int b : ms) cout << b << ' '; cout << endl;
		for(int i = 0; i <= mx_blk; i++) {
			cout << i << " :: " << endl;
			chunk[i].print();
		}
	}

	//cout << "finished Printing" << endl;

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

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

	//cout << "here" << endl;
	return ret;
}

컴파일 시 표준 에러 (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:49: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:79:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(it == x.size()) { return ii(0, _x); }
      ~~~^~~~~~~~~~~
elephants.cpp: In member function 'void bucket::print()':
elephants.cpp:83:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(int b : x) cout << b << ' '; cout << endl;
   ^~~
elephants.cpp:83:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(int b : x) cout << b << ' '; cout << endl;
                                    ^~~~
elephants.cpp:84:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(int b : cnt) cout << b << ' '; cout << endl;
   ^~~
elephants.cpp:84:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(int b : cnt) cout << b << ' '; cout << endl;
                                      ^~~~
elephants.cpp:85:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(int b : last) cout << b << ' '; cout << endl;
   ^~~
elephants.cpp:85:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(int b : last) cout << b << ' '; cout << endl;
                                       ^~~~
elephants.cpp: In function 'void refresh()':
elephants.cpp:95:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < X.size(); i++) temp[i] = X[to[i]];
                 ~~^~~~~~~~~~
elephants.cpp:96:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < X.size(); i++) to[i] = i;
                 ~~^~~~~~~~~~
elephants.cpp:101:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < X.size(); i++) {
                 ~~^~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:170:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for(int b : ms) cout << b << ' '; cout << endl;
   ^~~
elephants.cpp:170:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for(int b : ms) cout << b << ' '; cout << endl;
                                     ^~~~

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