oj.uz

Submission #351820

# Submission time Handle Problem Language Result Execution time Memory
351820 2021-01-20T08:26:23 Z juggernaut Dancing Elephants (IOI11_elephants) C++14
100 / 100
 5600 ms 17264 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:19:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   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:61:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   if(p<v[i].size()) {
      |      ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 316 ms 2828 KB Output is correct
8 Correct 353 ms 3328 KB Output is correct
9 Correct 457 ms 5740 KB Output is correct
10 Correct 519 ms 5740 KB Output is correct
11 Correct 542 ms 5612 KB Output is correct
12 Correct 890 ms 5964 KB Output is correct
13 Correct 476 ms 5532 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 316 ms 2828 KB Output is correct
8 Correct 353 ms 3328 KB Output is correct
9 Correct 457 ms 5740 KB Output is correct
10 Correct 519 ms 5740 KB Output is correct
11 Correct 542 ms 5612 KB Output is correct
12 Correct 890 ms 5964 KB Output is correct
13 Correct 476 ms 5532 KB Output is correct
14 Correct 275 ms 4252 KB Output is correct
15 Correct 526 ms 4460 KB Output is correct
16 Correct 1238 ms 6508 KB Output is correct
17 Correct 1458 ms 8512 KB Output is correct
18 Correct 1504 ms 8084 KB Output is correct
19 Correct 800 ms 8152 KB Output is correct
20 Correct 1485 ms 8188 KB Output is correct
21 Correct 1474 ms 8012 KB Output is correct
22 Correct 735 ms 7660 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 316 ms 2828 KB Output is correct
8 Correct 353 ms 3328 KB Output is correct
9 Correct 457 ms 5740 KB Output is correct
10 Correct 519 ms 5740 KB Output is correct
11 Correct 542 ms 5612 KB Output is correct
12 Correct 890 ms 5964 KB Output is correct
13 Correct 476 ms 5532 KB Output is correct
14 Correct 275 ms 4252 KB Output is correct
15 Correct 526 ms 4460 KB Output is correct
16 Correct 1238 ms 6508 KB Output is correct
17 Correct 1458 ms 8512 KB Output is correct
18 Correct 1504 ms 8084 KB Output is correct
19 Correct 800 ms 8152 KB Output is correct
20 Correct 1485 ms 8188 KB Output is correct
21 Correct 1474 ms 8012 KB Output is correct
22 Correct 735 ms 7660 KB Output is correct
23 Correct 3548 ms 14572 KB Output is correct
24 Correct 3646 ms 14652 KB Output is correct
25 Correct 2803 ms 17212 KB Output is correct
26 Correct 3002 ms 17264 KB Output is correct
27 Correct 3353 ms 17052 KB Output is correct
28 Correct 1493 ms 5908 KB Output is correct
29 Correct 1413 ms 5764 KB Output is correct
30 Correct 1476 ms 5808 KB Output is correct
31 Correct 1423 ms 5668 KB Output is correct
32 Correct 3344 ms 16636 KB Output is correct
33 Correct 1467 ms 15892 KB Output is correct
34 Correct 3432 ms 16876 KB Output is correct
35 Correct 1460 ms 17132 KB Output is correct
36 Correct 81 ms 7148 KB Output is correct
37 Correct 2131 ms 17260 KB Output is correct
38 Correct 2862 ms 15980 KB Output is correct
39 Correct 3005 ms 16876 KB Output is correct
40 Correct 3085 ms 15948 KB Output is correct
41 Correct 5365 ms 16944 KB Output is correct
42 Correct 5600 ms 17124 KB Output is correct