oj.uz

Submission #584457

# Submission time Handle Problem Language Result Execution time Memory
584457 2022-06-27T12:07:39 Z benson1029 Dancing Elephants (IOI11_elephants) C++14
100 / 100
 6889 ms 24496 KB 
#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;

int n;
int RTN;
int cntGRP;
int l;
int a[150005];
int grp[150005];
vector<int> grpv[150005], dis[150005], nxt[150005];
vector< pair<int,int> > v;
int round_cnt = 0;

void calcgroup(int i) {
	dis[i].resize(grpv[i].size());
	nxt[i].resize(grpv[i].size());
	int ptr = grpv[i].size()-1;
	for(int j=grpv[i].size()-1; j>=0; j--) {
		while(ptr > 0 && grpv[i][ptr] - grpv[i][j] > l) ptr--;
		if(ptr == grpv[i].size()-1) {
			dis[i][j] = 1;
			nxt[i][j] = grpv[i][j] + l + 1;
		} else {
			dis[i][j] = dis[i][ptr+1] + 1;
			nxt[i][j] = nxt[i][ptr+1];
		}
	}
}

void build() {
	v.clear();
	for(int i=0; i<n; i++) {
		v.push_back({a[i], i});
	}
	sort(v.begin(), v.end());
	for(int i=0; i<cntGRP; i++) grpv[i].clear();
	for(int i=0; i<n; i++) {
		grp[v[i].second] = i/RTN;
		grpv[i/RTN].push_back(v[i].first);
	}
	for(int i=0; i<cntGRP; i++) {
		calcgroup(i);
	}
}

void init(int N, int L, int X[])
{
	n = N; l = L;
	RTN = ceil(sqrt(n));
	cntGRP = (N-1) / RTN + 1;
	for(int i=0; i<n; i++) a[i] = X[i];
	build();
}

int update(int i, int y)
{
	++round_cnt;
	if(round_cnt % RTN == 0) {
		a[i] = y;
		build();
	} else {
		int origgrp = 0;
		while(origgrp < cntGRP-1 && a[i] >= grpv[origgrp+1][0]) origgrp++;

		int newgrp = 0;
		while(newgrp < cntGRP-1 && y >= grpv[newgrp+1][0]) newgrp++;

		for(int j=0; j<grpv[origgrp].size(); j++) {
			if(grpv[origgrp][j] == a[i]) {
				for(int k=j+1; k<grpv[origgrp].size(); k++) grpv[origgrp][k-1] = grpv[origgrp][k];
				grpv[origgrp].pop_back();
				break;
			}
		}
		calcgroup(origgrp);

		a[i] = y;
		grpv[newgrp].push_back(y);
		int ptr = grpv[newgrp].size()-1;
		while(ptr > 0 && grpv[newgrp][ptr-1] > grpv[newgrp][ptr]) {
			swap(grpv[newgrp][ptr-1], grpv[newgrp][ptr]);
			ptr--;
		}
		calcgroup(newgrp);
	}

	// calculate answer

	int prevv = -2e9;
	int ans = 0;
	for(int i=0; i<cntGRP; i++) {
		if(grpv[i].size() == 0 || prevv > grpv[i][grpv[i].size()-1]) {
			continue;
		}
		int pos = lower_bound(grpv[i].begin(), grpv[i].end(), prevv) - grpv[i].begin();
		ans += dis[i][pos];
		prevv = nxt[i][pos];
	}
	return ans;
}

Compilation message

elephants.cpp: In function 'void calcgroup(int)':
elephants.cpp:21:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   if(ptr == grpv[i].size()-1) {
      |      ~~~~^~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:69:17: 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<grpv[origgrp].size(); j++) {
      |                ~^~~~~~~~~~~~~~~~~~~~~
elephants.cpp:71:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int k=j+1; k<grpv[origgrp].size(); k++) grpv[origgrp][k-1] = grpv[origgrp][k];
      |                    ~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10836 KB Output is correct
2 Correct 6 ms 10876 KB Output is correct
3 Correct 6 ms 10860 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10836 KB Output is correct
2 Correct 6 ms 10876 KB Output is correct
3 Correct 6 ms 10860 KB Output is correct
4 Correct 7 ms 10836 KB Output is correct
5 Correct 7 ms 10820 KB Output is correct
6 Correct 6 ms 10836 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10836 KB Output is correct
2 Correct 6 ms 10876 KB Output is correct
3 Correct 6 ms 10860 KB Output is correct
4 Correct 7 ms 10836 KB Output is correct
5 Correct 7 ms 10820 KB Output is correct
6 Correct 6 ms 10836 KB Output is correct
7 Correct 351 ms 12252 KB Output is correct
8 Correct 400 ms 12620 KB Output is correct
9 Correct 642 ms 13884 KB Output is correct
10 Correct 797 ms 13620 KB Output is correct
11 Correct 765 ms 14388 KB Output is correct
12 Correct 1279 ms 14956 KB Output is correct
13 Correct 810 ms 14240 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10836 KB Output is correct
2 Correct 6 ms 10876 KB Output is correct
3 Correct 6 ms 10860 KB Output is correct
4 Correct 7 ms 10836 KB Output is correct
5 Correct 7 ms 10820 KB Output is correct
6 Correct 6 ms 10836 KB Output is correct
7 Correct 351 ms 12252 KB Output is correct
8 Correct 400 ms 12620 KB Output is correct
9 Correct 642 ms 13884 KB Output is correct
10 Correct 797 ms 13620 KB Output is correct
11 Correct 765 ms 14388 KB Output is correct
12 Correct 1279 ms 14956 KB Output is correct
13 Correct 810 ms 14240 KB Output is correct
14 Correct 788 ms 14064 KB Output is correct
15 Correct 715 ms 14076 KB Output is correct
16 Correct 1920 ms 15544 KB Output is correct
17 Correct 2178 ms 16772 KB Output is correct
18 Correct 2248 ms 16812 KB Output is correct
19 Correct 1385 ms 16364 KB Output is correct
20 Correct 2116 ms 16836 KB Output is correct
21 Correct 2129 ms 16744 KB Output is correct
22 Correct 1375 ms 15788 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10836 KB Output is correct
2 Correct 6 ms 10876 KB Output is correct
3 Correct 6 ms 10860 KB Output is correct
4 Correct 7 ms 10836 KB Output is correct
5 Correct 7 ms 10820 KB Output is correct
6 Correct 6 ms 10836 KB Output is correct
7 Correct 351 ms 12252 KB Output is correct
8 Correct 400 ms 12620 KB Output is correct
9 Correct 642 ms 13884 KB Output is correct
10 Correct 797 ms 13620 KB Output is correct
11 Correct 765 ms 14388 KB Output is correct
12 Correct 1279 ms 14956 KB Output is correct
13 Correct 810 ms 14240 KB Output is correct
14 Correct 788 ms 14064 KB Output is correct
15 Correct 715 ms 14076 KB Output is correct
16 Correct 1920 ms 15544 KB Output is correct
17 Correct 2178 ms 16772 KB Output is correct
18 Correct 2248 ms 16812 KB Output is correct
19 Correct 1385 ms 16364 KB Output is correct
20 Correct 2116 ms 16836 KB Output is correct
21 Correct 2129 ms 16744 KB Output is correct
22 Correct 1375 ms 15788 KB Output is correct
23 Correct 3951 ms 23096 KB Output is correct
24 Correct 4266 ms 23348 KB Output is correct
25 Correct 3302 ms 23144 KB Output is correct
26 Correct 4669 ms 22584 KB Output is correct
27 Correct 5168 ms 22452 KB Output is correct
28 Correct 1114 ms 15880 KB Output is correct
29 Correct 1096 ms 15776 KB Output is correct
30 Correct 1126 ms 15772 KB Output is correct
31 Correct 1046 ms 15876 KB Output is correct
32 Correct 4224 ms 22004 KB Output is correct
33 Correct 4310 ms 21260 KB Output is correct
34 Correct 4261 ms 22152 KB Output is correct
35 Correct 4365 ms 22460 KB Output is correct
36 Correct 3273 ms 22000 KB Output is correct
37 Correct 6698 ms 24496 KB Output is correct
38 Correct 4346 ms 21180 KB Output is correct
39 Correct 4417 ms 22268 KB Output is correct
40 Correct 4372 ms 21168 KB Output is correct
41 Correct 6683 ms 23132 KB Output is correct
42 Correct 6889 ms 23432 KB Output is correct