Submission #574683

#	Time	Username	Problem	Language	Result	Execution time	Memory
574683		keta_tsimakuridze	Dancing Elephants (IOI11_elephants)	C++17	0 / 100	1 ms	340 KiB

elephants

#include "elephants.h"
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int maxn = 2e5 + 5, SQ = 400;
int n, b[maxn], p[maxn], c[maxn], Len, Bl, en[maxn];
vector<int> x[SQ];
void calc(vector<int> v) {
	int l = (int)v.size(); --l;
	for(int j = (int)v.size() - 1; j >= 0; j--) {
		while(p[v[j]] + Len < p[v[l]]) --l;
		if(l == (int)v.size() - 1) c[v[j]] = 1, en[v[j]] = p[v[j]] + Len;
		else c[v[j]] = c[v[l + 1]] + 1, en[v[j]] = en[v[l + 1]];
	}
}
void init(int m, int l, int a[])
{	n = m; Len = l;
	for(int i = 0; i < n; i++) p[i] = a[i];

	Bl = sqrt(n);
	for(int i = 0; i < n; i++) {
		x[i / Bl].push_back(i);
		b[i] = i / Bl;
	}
	for(int i = 0; i <= (n - 1) / Bl; i++)  calc(x[i]);
}

int update(int id, int y)
{
	for(int i = 0; i < x[b[id]].size(); i++) {
		if(x[b[id]][i] == id) {
			vector<int> v;
			for(int j = 0; j < i; j++) v.push_back(x[b[id]][j]);
			for(int j = i + 1; j < x[b[id]].size(); j++) v.push_back(x[b[id]][j]);
			x[b[id]] = v;
			calc(x[b[id]]);
			break;
		}
	}
	int last = 2e9, bl = (n - 1) / Bl;
	for(int i = (n - 1) / Bl; i >= 0; i--) {
		if(last >= y) {
			bl = i;
		}
		if(x[i].size()) last = p[x[i][0]];
	}
	b[id] = bl;
	vector<int> v;
	for(int i = 0; i < x[bl].size(); i++) {
		if(p[x[bl][i]] >= y) break;
		v.push_back(x[bl][i]);
	}
	v.push_back(id);
	for(int i = 0; i < x[bl].size(); i++) {
        if(p[x[bl][i]] >= y) v.push_back(x[bl][i]);
	}
	x[bl] = v;
	p[id] = y;
	int ff = 0;
	for(int i = 0; i <= (n - 1) / Bl; i++) {
		if((!x[i].size() && i < (n - 1) / Bl) || x[i].size() >= 2 * Bl) {
			ff = 1;
		}
	}
	if(ff) {
		vector<int> v;
		for(int i = 0; i <= (n - 1) / Bl; i++) {
			for(int j = 0; j < x[i].size(); i++) {
				v.push_back(x[i][j]);
			}
		}
		for(int i = 0; i < n; i++) x[i / Bl].push_back(v[i]), b[v[i]] = i / Bl;
		for(int i = 0; i <= (n - 1) / Bl; i++) calc(x[i]);
	} else calc(x[bl]);

	int cur = x[0][0];
	int ans = 0;
	while(true) {
		ans += c[cur];
		int l = b[cur] + 1, r = (n - 1) / Bl, nxt = -1;
		while(l <= r) {
            int mid = (l + r) / 2;
            if(!x[mid].size()) {
                r = mid - 1; continue;
            }
            if(p[x[mid].back()] > en[cur]) nxt = mid, r = mid - 1;
            else l = mid + 1;
		}
		if(nxt == -1) break;
		l = 0, r = x[nxt].size(); r--;
		int b = 0;
		while(l <= r) {
            int mid = (l + r) / 2;
            if(p[x[nxt][mid]] > en[cur]) b = mid, r = mid - 1;
            else l = mid + 1;
		}
		cur = x[nxt][b];
	}
	return ans;
}

Compilation message (stderr)

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int i = 0; i < x[b[id]].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~
elephants.cpp:35:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |    for(int j = i + 1; j < x[b[id]].size(); j++) v.push_back(x[b[id]][j]);
      |                       ~~^~~~~~~~~~~~~~~~~
elephants.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for(int i = 0; i < x[bl].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~
elephants.cpp:55:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(int i = 0; i < x[bl].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~
elephants.cpp:62:56: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |   if((!x[i].size() && i < (n - 1) / Bl) || x[i].size() >= 2 * Bl) {
      |                                            ~~~~~~~~~~~~^~~~~~~~~
elephants.cpp:69:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |    for(int j = 0; j < x[i].size(); i++) {
      |                   ~~^~~~~~~~~~~~~

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