oj.uz

Submission #132578

# Submission time Handle Problem Language Result Execution time Memory
132578 2019-07-19T07:41:58 Z tmwilliamlin168 Dancing Elephants (IOI11_elephants) C++14
100 / 100
 6159 ms 12280 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;

const int mxN=1.5e5, B=400, mxBC=(mxN-1)/B+1;
int n, l, *x, uc, bc, r[mxBC];
map<int, int> mp;
vector<int> v[mxBC];
vector<array<int, 2>> w[mxBC];

void init(int N, int L, int X[]) {
	n=N;
	l=L;
	x=X;
	for(int i=0; i<n; ++i)
		++mp[x[i]];
}

void bb(int i) {
	w[i]=vector<array<int, 2>>(v[i].size());
	for(int j1=(int)v[i].size()-1, j2=v[i].size(); ~j1; --j1) {
		while(v[i][j2-1]>v[i][j1]+l)
			--j2;
		w[i][j1]=j2<v[i].size()?array<int, 2>{w[i][j2][0]+1, w[i][j2][1]}:array<int, 2>{1, v[i][j1]+l};
	}
}
void bld() {
	bc=0;
	for(pair<int, int> p : mp) {
		if(!bc||v[bc-1].size()>=B)
			v[bc++].clear();
		v[bc-1].push_back(p.first);
	}
	for(int i=0; i<bc; ++i) {
		r[i]=i+1<bc?v[i+1][0]-1:1e9;
		bb(i);
	}
}

void upd(int x, bool a) {
	int c=-1;
	while(x>r[++c]);
	int p=lower_bound(v[c].begin(), v[c].end(), x)-v[c].begin();
	if(a)
		v[c].insert(v[c].begin()+p, x);
	else
		v[c].erase(v[c].begin()+p);
	bb(c);
}

int update(int i, int y) {
	if(uc++%B==0)
		bld();
	--mp[x[i]];
	if(!mp[x[i]]) {
		upd(x[i], 0);
		mp.erase(x[i]);
	}
	if(!mp[y])
		upd(y, 1);
	++mp[y];
	x[i]=y;
	int a=0;
	for(int i=0, c=-1; i<bc; ++i) {
		int p=upper_bound(v[i].begin(), v[i].end(), c)-v[i].begin();
		if(p<v[i].size()) {
			a+=w[i][p][0];
			c=w[i][p][1];
		}
	}
	return a;
}

Compilation message

elephants.cpp: In function 'void bb(int)':
elephants.cpp:24:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   w[i][j1]=j2<v[i].size()?array<int, 2>{w[i][j2][0]+1, w[i][j2][1]}:array<int, 2>{1, v[i][j1]+l};
            ~~^~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:66:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(p<v[i].size()) {
      ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 375 ms 1824 KB Output is correct
8 Correct 403 ms 2140 KB Output is correct
9 Correct 464 ms 4224 KB Output is correct
10 Correct 444 ms 4220 KB Output is correct
11 Correct 469 ms 4216 KB Output is correct
12 Correct 853 ms 4472 KB Output is correct
13 Correct 454 ms 4216 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 375 ms 1824 KB Output is correct
8 Correct 403 ms 2140 KB Output is correct
9 Correct 464 ms 4224 KB Output is correct
10 Correct 444 ms 4220 KB Output is correct
11 Correct 469 ms 4216 KB Output is correct
12 Correct 853 ms 4472 KB Output is correct
13 Correct 454 ms 4216 KB Output is correct
14 Correct 249 ms 2552 KB Output is correct
15 Correct 614 ms 2872 KB Output is correct
16 Correct 1236 ms 4628 KB Output is correct
17 Correct 1460 ms 5752 KB Output is correct
18 Correct 1562 ms 5860 KB Output is correct
19 Correct 855 ms 5752 KB Output is correct
20 Correct 1568 ms 6008 KB Output is correct
21 Correct 1489 ms 5968 KB Output is correct
22 Correct 897 ms 5752 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 375 ms 1824 KB Output is correct
8 Correct 403 ms 2140 KB Output is correct
9 Correct 464 ms 4224 KB Output is correct
10 Correct 444 ms 4220 KB Output is correct
11 Correct 469 ms 4216 KB Output is correct
12 Correct 853 ms 4472 KB Output is correct
13 Correct 454 ms 4216 KB Output is correct
14 Correct 249 ms 2552 KB Output is correct
15 Correct 614 ms 2872 KB Output is correct
16 Correct 1236 ms 4628 KB Output is correct
17 Correct 1460 ms 5752 KB Output is correct
18 Correct 1562 ms 5860 KB Output is correct
19 Correct 855 ms 5752 KB Output is correct
20 Correct 1568 ms 6008 KB Output is correct
21 Correct 1489 ms 5968 KB Output is correct
22 Correct 897 ms 5752 KB Output is correct
23 Correct 4413 ms 11756 KB Output is correct
24 Correct 4249 ms 11776 KB Output is correct
25 Correct 3504 ms 11820 KB Output is correct
26 Correct 3805 ms 11896 KB Output is correct
27 Correct 3907 ms 11772 KB Output is correct
28 Correct 1662 ms 2900 KB Output is correct
29 Correct 1578 ms 2680 KB Output is correct
30 Correct 1648 ms 2808 KB Output is correct
31 Correct 1619 ms 2808 KB Output is correct
32 Correct 3951 ms 11884 KB Output is correct
33 Correct 1258 ms 12012 KB Output is correct
34 Correct 3271 ms 11772 KB Output is correct
35 Correct 1288 ms 11764 KB Output is correct
36 Correct 77 ms 2680 KB Output is correct
37 Correct 2169 ms 12028 KB Output is correct
38 Correct 3440 ms 11768 KB Output is correct
39 Correct 3323 ms 11768 KB Output is correct
40 Correct 3522 ms 11768 KB Output is correct
41 Correct 5700 ms 12280 KB Output is correct
42 Correct 6159 ms 12112 KB Output is correct