oj.uz

Submission #574688

# Submission time Handle Problem Language Result Execution time Memory
574688 2022-06-09T09:01:46 Z keta_tsimakuridze Dancing Elephants (IOI11_elephants) C++17
100 / 100
 8057 ms 13024 KB 
#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(); 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 1 ms 340 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 369 ms 2128 KB Output is correct
8 Correct 478 ms 2416 KB Output is correct
9 Correct 781 ms 3692 KB Output is correct
10 Correct 954 ms 4080 KB Output is correct
11 Correct 847 ms 4032 KB Output is correct
12 Correct 990 ms 4096 KB Output is correct
13 Correct 1118 ms 3868 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 369 ms 2128 KB Output is correct
8 Correct 478 ms 2416 KB Output is correct
9 Correct 781 ms 3692 KB Output is correct
10 Correct 954 ms 4080 KB Output is correct
11 Correct 847 ms 4032 KB Output is correct
12 Correct 990 ms 4096 KB Output is correct
13 Correct 1118 ms 3868 KB Output is correct
14 Correct 657 ms 3464 KB Output is correct
15 Correct 748 ms 3328 KB Output is correct
16 Correct 1382 ms 4196 KB Output is correct
17 Correct 1876 ms 6008 KB Output is correct
18 Correct 1852 ms 5904 KB Output is correct
19 Correct 1835 ms 6268 KB Output is correct
20 Correct 1752 ms 5960 KB Output is correct
21 Correct 1721 ms 6000 KB Output is correct
22 Correct 1952 ms 5628 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 369 ms 2128 KB Output is correct
8 Correct 478 ms 2416 KB Output is correct
9 Correct 781 ms 3692 KB Output is correct
10 Correct 954 ms 4080 KB Output is correct
11 Correct 847 ms 4032 KB Output is correct
12 Correct 990 ms 4096 KB Output is correct
13 Correct 1118 ms 3868 KB Output is correct
14 Correct 657 ms 3464 KB Output is correct
15 Correct 748 ms 3328 KB Output is correct
16 Correct 1382 ms 4196 KB Output is correct
17 Correct 1876 ms 6008 KB Output is correct
18 Correct 1852 ms 5904 KB Output is correct
19 Correct 1835 ms 6268 KB Output is correct
20 Correct 1752 ms 5960 KB Output is correct
21 Correct 1721 ms 6000 KB Output is correct
22 Correct 1952 ms 5628 KB Output is correct
23 Correct 4808 ms 10844 KB Output is correct
24 Correct 5278 ms 10864 KB Output is correct
25 Correct 5378 ms 10852 KB Output is correct
26 Correct 6992 ms 12576 KB Output is correct
27 Correct 6640 ms 12452 KB Output is correct
28 Correct 780 ms 5268 KB Output is correct
29 Correct 726 ms 5272 KB Output is correct
30 Correct 796 ms 5312 KB Output is correct
31 Correct 748 ms 5264 KB Output is correct
32 Correct 5662 ms 12036 KB Output is correct
33 Correct 4119 ms 11288 KB Output is correct
34 Correct 6179 ms 12136 KB Output is correct
35 Correct 4484 ms 13024 KB Output is correct
36 Correct 3609 ms 12216 KB Output is correct
37 Correct 6138 ms 12296 KB Output is correct
38 Correct 7144 ms 11344 KB Output is correct
39 Correct 6563 ms 12308 KB Output is correct
40 Correct 8057 ms 11224 KB Output is correct
41 Correct 6455 ms 11900 KB Output is correct
42 Correct 6069 ms 12124 KB Output is correct