oj.uz

Submission #132581

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

const int mxN=1.5e5, B=550, 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:22: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:64: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 503 ms 1836 KB Output is correct
8 Correct 535 ms 2188 KB Output is correct
9 Correct 486 ms 4472 KB Output is correct
10 Correct 462 ms 4216 KB Output is correct
11 Correct 517 ms 4216 KB Output is correct
12 Correct 898 ms 4728 KB Output is correct
13 Correct 478 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 503 ms 1836 KB Output is correct
8 Correct 535 ms 2188 KB Output is correct
9 Correct 486 ms 4472 KB Output is correct
10 Correct 462 ms 4216 KB Output is correct
11 Correct 517 ms 4216 KB Output is correct
12 Correct 898 ms 4728 KB Output is correct
13 Correct 478 ms 4216 KB Output is correct
14 Correct 282 ms 2616 KB Output is correct
15 Correct 792 ms 2952 KB Output is correct
16 Correct 1328 ms 4644 KB Output is correct
17 Correct 1432 ms 6116 KB Output is correct
18 Correct 1535 ms 6136 KB Output is correct
19 Correct 806 ms 5876 KB Output is correct
20 Correct 1572 ms 5980 KB Output is correct
21 Correct 1475 ms 6132 KB Output is correct
22 Correct 668 ms 5864 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 503 ms 1836 KB Output is correct
8 Correct 535 ms 2188 KB Output is correct
9 Correct 486 ms 4472 KB Output is correct
10 Correct 462 ms 4216 KB Output is correct
11 Correct 517 ms 4216 KB Output is correct
12 Correct 898 ms 4728 KB Output is correct
13 Correct 478 ms 4216 KB Output is correct
14 Correct 282 ms 2616 KB Output is correct
15 Correct 792 ms 2952 KB Output is correct
16 Correct 1328 ms 4644 KB Output is correct
17 Correct 1432 ms 6116 KB Output is correct
18 Correct 1535 ms 6136 KB Output is correct
19 Correct 806 ms 5876 KB Output is correct
20 Correct 1572 ms 5980 KB Output is correct
21 Correct 1475 ms 6132 KB Output is correct
22 Correct 668 ms 5864 KB Output is correct
23 Correct 3710 ms 12072 KB Output is correct
24 Correct 3586 ms 12408 KB Output is correct
25 Correct 2972 ms 12080 KB Output is correct
26 Correct 3046 ms 12260 KB Output is correct
27 Correct 3352 ms 12228 KB Output is correct
28 Correct 2152 ms 2916 KB Output is correct
29 Correct 2047 ms 2808 KB Output is correct
30 Correct 2188 ms 2860 KB Output is correct
31 Correct 2044 ms 2804 KB Output is correct
32 Correct 3521 ms 12156 KB Output is correct
33 Correct 1094 ms 12344 KB Output is correct
34 Correct 2973 ms 12112 KB Output is correct
35 Correct 1247 ms 12152 KB Output is correct
36 Correct 77 ms 2680 KB Output is correct
37 Correct 1975 ms 12380 KB Output is correct
38 Correct 3051 ms 12152 KB Output is correct
39 Correct 2870 ms 12212 KB Output is correct
40 Correct 2927 ms 12152 KB Output is correct
41 Correct 5392 ms 12616 KB Output is correct
42 Correct 5647 ms 12320 KB Output is correct