제출 #931361

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
931361		hqminhuwu	코끼리 (Dancing Elephants) (IOI11_elephants)	C++14	100 / 100	5499 ms	37100 KiB

elephants

#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(int _a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"


using namespace std;
const int nn = 5e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;
const int uwu = 400;

int nl, n;

struct block {
	vector <pii> v;
	int cnt[2 * uwu + 1], pos[2 * uwu + 1];

	void build (){
		if (v.empty()) return;
		int r = v.size();
		r--;
		cnt[r] = 1, pos[r] = v[r].st;
		ford (l, r, 0){
			while (v[r].st - v[l].st > nl)
				r--;
			if (r == v.size() - 1)
				cnt[l] = 1, pos[l] = v[l].st;
			else cnt[l] = cnt[r + 1] + 1, pos[l] = pos[r + 1];
		}
	}

	void ins (int val, int id){
		v.pb({val, id});
		int i = v.size();
		i--;

		while (i > 0 && v[i] < v[i - 1])
			swap(v[i], v[i - 1]), i--;
	}

	void ers (int id){
		int j;
		forf (i, 0, v.size())
		if (v[i].nd == id)
			j = i;
		forf (i, j, v.size() - 1)
			swap(v[i], v[i + 1]);
		v.pop_back();
	}

	pii get (int u){
		if (u + nl >= v.back().st)
			return {u, 0};
	//	cout << "get " << v.back().st << " " << v.back().nd << "\n";
		int k = upper_bound(all(v), mp(u + nl, 1000000)) - v.begin();
		return {pos[k], cnt[k]};
	}

	void debug (){
		// forf (i, 0, v.size())
		// 	cout <<v[i].st << " " << v[i].nd << " " << cnt[i] << " " << pos[i] << "\n";
	}
};

block b[uwu + 1000];
pii a[nn];
int pos[nn], cnt;

void rs (){
	int j = 0;
	forr (i, 0, uwu)
		for (pii w : b[i].v)
			a[++j] = w;

	// forr (i, 1, n)
	// 	cout << a[i].st << " " << a[i].nd << "\n";
	forr (i, 0, uwu)
		b[i].v.clear();

	forr (i, 1, n)
		b[i / uwu].ins(a[i].st, a[i].nd), pos[a[i].nd] = i / uwu;

	forr (i, 0, uwu)
		b[i].build(), b[i].debug();
}

void debug(){
	forr (i, 0, uwu)
		cout << i << ":\n",b[i].debug();
}

void init (int _n, int _l, int _x[]){
	n = _n;
	nl = _l;
	forr (i, 1, n)
		a[i].st = _x[i - 1], a[i].nd = i;
	sort(a + 1, a + 1 + n);
	rs();
}

int update (int u, int w){

	//cout << L << "\n";
	if (cnt > uwu)
		rs(), cnt = 0;
	cnt++;

	//return 0;

	int j = uwu;

	forr (i, 1, uwu){
		if (b[i].v.empty()) {
			j = i - 1;
			break;
		}

		if (b[i].v[0].st > w){
			j = i - 1;
			break;
		}
	}

	u++;

	b[pos[u]].ers(u);
	b[pos[u]].build();
	b[j].ins(w, u);
	b[j].build();
	pos[u] = j;

	//debug();

	int d = 0, ans = 0;

	forr (i, 0, uwu)
	if (!b[i].v.empty()){
		d = b[i].v[0].st;
		break;
	}
	forr (i, 0, uwu){
		//cout << d <<  " " << ans << "\n";
		if (b[i].v.empty()) continue;
		pii tmp = b[i].get(d);
		d = tmp.st;
		ans += tmp.nd;
	}

	return ans + 1;
}

컴파일 시 표준 에러 (stderr) 메시지

elephants.cpp: In member function 'void block::build()':
elephants.cpp:39:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |    if (r == v.size() - 1)
      |        ~~^~~~~~~~~~~~~~~
elephants.cpp: In member function 'void block::ers(int)':
elephants.cpp:4:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
      |                                              ^
elephants.cpp:56:3: note: in expansion of macro 'forf'
   56 |   forf (i, 0, v.size())
      |   ^~~~
elephants.cpp:4:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
      |                                              ^
elephants.cpp:59:3: note: in expansion of macro 'forf'
   59 |   forf (i, j, v.size() - 1)
      |   ^~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:59:9: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |   forf (i, j, v.size() - 1)
      |         ^
elephants.cpp:55:7: note: 'j' was declared here
   55 |   int j;
      |       ^

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