Submission #574690

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
574690	2022-06-09T09:04:08 Z	keta_tsimakuridze	Dancing Elephants (IOI11_elephants)	C++17	100 / 100	5773 ms	7944 KB

elephants

//#include "elephants.h"
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int maxn = 2e5 + 5, SQ = 700;
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 = min(n, 700);
	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(); j++) {
				v.push_back(x[i][j]);
			}
			x[i].clear();
		}
		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

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(); j++) {
      |                   ~~^~~~~~~~~~~~~

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct

Subtask #2

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct

Subtask #3

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	806 ms	1260 KB	Output is correct
8	Correct	791 ms	1388 KB	Output is correct
9	Correct	896 ms	2216 KB	Output is correct
10	Correct	762 ms	2704 KB	Output is correct
11	Correct	834 ms	2812 KB	Output is correct
12	Correct	1398 ms	2668 KB	Output is correct
13	Correct	845 ms	2792 KB	Output is correct

Subtask #4

47.0 / 47.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	806 ms	1260 KB	Output is correct
8	Correct	791 ms	1388 KB	Output is correct
9	Correct	896 ms	2216 KB	Output is correct
10	Correct	762 ms	2704 KB	Output is correct
11	Correct	834 ms	2812 KB	Output is correct
12	Correct	1398 ms	2668 KB	Output is correct
13	Correct	845 ms	2792 KB	Output is correct
14	Correct	1142 ms	1880 KB	Output is correct
15	Correct	1177 ms	1784 KB	Output is correct
16	Correct	1914 ms	2448 KB	Output is correct
17	Correct	2012 ms	3856 KB	Output is correct
18	Correct	2110 ms	3804 KB	Output is correct
19	Correct	1493 ms	3780 KB	Output is correct
20	Correct	2071 ms	3744 KB	Output is correct
21	Correct	2028 ms	3852 KB	Output is correct
22	Correct	1538 ms	3772 KB	Output is correct

Subtask #5

3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	806 ms	1260 KB	Output is correct
8	Correct	791 ms	1388 KB	Output is correct
9	Correct	896 ms	2216 KB	Output is correct
10	Correct	762 ms	2704 KB	Output is correct
11	Correct	834 ms	2812 KB	Output is correct
12	Correct	1398 ms	2668 KB	Output is correct
13	Correct	845 ms	2792 KB	Output is correct
14	Correct	1142 ms	1880 KB	Output is correct
15	Correct	1177 ms	1784 KB	Output is correct
16	Correct	1914 ms	2448 KB	Output is correct
17	Correct	2012 ms	3856 KB	Output is correct
18	Correct	2110 ms	3804 KB	Output is correct
19	Correct	1493 ms	3780 KB	Output is correct
20	Correct	2071 ms	3744 KB	Output is correct
21	Correct	2028 ms	3852 KB	Output is correct
22	Correct	1538 ms	3772 KB	Output is correct
23	Correct	4072 ms	6032 KB	Output is correct
24	Correct	4319 ms	5912 KB	Output is correct
25	Correct	3851 ms	5908 KB	Output is correct
26	Correct	4008 ms	7544 KB	Output is correct
27	Correct	4839 ms	7592 KB	Output is correct
28	Correct	3474 ms	2400 KB	Output is correct
29	Correct	3438 ms	2332 KB	Output is correct
30	Correct	3537 ms	2344 KB	Output is correct
31	Correct	3435 ms	2432 KB	Output is correct
32	Correct	4137 ms	7652 KB	Output is correct
33	Correct	2940 ms	7556 KB	Output is correct
34	Correct	3789 ms	7672 KB	Output is correct
35	Correct	3880 ms	7944 KB	Output is correct
36	Correct	3842 ms	7600 KB	Output is correct
37	Correct	4944 ms	6008 KB	Output is correct
38	Correct	4380 ms	7584 KB	Output is correct
39	Correct	4513 ms	7832 KB	Output is correct
40	Correct	4952 ms	7672 KB	Output is correct
41	Correct	5600 ms	7584 KB	Output is correct
42	Correct	5773 ms	7536 KB	Output is correct