oj.uz

Submission #151337

# Submission time Handle Problem Language Result Execution time Memory
151337 2019-09-02T13:22:01 Z GioChkhaidze Dancing Elephants (IOI11_elephants) C++14
100 / 100
 5468 ms 15208 KB 
#include <bits/stdc++.h>
#include "elephants.h"

using namespace std;

const int Na=150006;
const int Nq=400;

int n,m,Ms,l,Updcnt,A[Na];

int Lmax[Nq][3*Nq];
int Llen[Nq][3*Nq];

vector < int > v[Nq];

void process_block(int x) {
	int r=v[x].size()-1,rmax=v[x][v[x].size()-1];
	
	for (int i=v[x].size()-1; i>=0; i--) {
		int pos=v[x][i];
		if (pos+l>=v[x][r]) {
			Lmax[x][i]=pos+l;
			Llen[x][i]=1;
		}
			else  {
			while (0<r && pos+l<v[x][r-1]) 
				r--;
			Lmax[x][i]=Lmax[x][r];
			Llen[x][i]=Llen[x][r]+1;
		}
	}
}

int get_ans() {
	int res=0,cur_block=0;
	
	while (cur_block<Ms && !v[cur_block].size())
		cur_block++;
	
	int pos=v[cur_block][0],idx=0;
	
	while (cur_block<Ms) {
		int Lmx=Lmax[cur_block][idx];
		res+=Llen[cur_block][idx];
	
		while (cur_block<Ms) {
			cur_block++;
			if (!v[cur_block].size()) continue;
			if (Lmx<v[cur_block][v[cur_block].size()-1]) {
				int l=0,r=v[cur_block].size()-1,mid;
				
				while (l<=r) {
					mid=(l+r)/2;
					
					if (Lmx<v[cur_block][mid]) { idx=mid; r=mid-1; }
									   				 	   else l=mid+1;
				}

				break;
			}
		}	
	}
	
	return res;
}

void restart() {
	vector < int > h;
	
	for (int i=0; i<Ms; i++) {
		for (int j=0; j<v[i].size(); j++) 
			h.push_back(v[i][j]);
			v[i].clear();
	}
	
	for (int i=0; i<h.size(); i++) 
		v[i/m].push_back(h[i]);
	
	for (int i=0; i<Ms; i++)
		process_block(i);
}

void del(int x) {
	int cur_block=-1;
	
	while (cur_block<Ms) {
		cur_block++;
		if (!v[cur_block].size()) continue;
		if (v[cur_block][v[cur_block].size()-1]<x) continue;
		
		for (int j=0; j<v[cur_block].size(); j++) 
			if (v[cur_block][j]==x)  {
				v[cur_block].erase(v[cur_block].begin()+j);
				break;	
			}
		
		break;
	}
	
	process_block(cur_block);
}

void ins(int x) {
	int cur_block=-1;
	
	while (cur_block<Ms) {
		cur_block++;
		if (!v[cur_block].size()) continue;
		if (v[cur_block][v[cur_block].size()-1]<=x) continue;
		
		for (int j=0; j<v[cur_block].size(); j++) 
			if (x<v[cur_block][j]) {
				v[cur_block].insert(v[cur_block].begin()+j,x);
				break;	
			}
		
		break;
	}
	
	if (cur_block==Ms) {
		cur_block--;
		v[cur_block].push_back(x);
	}
	
	process_block(cur_block);
}

int update(int id, int nv) {
	del(A[id]);
	A[id]=nv;
	ins(A[id]);
	Updcnt++;
	
	if (!(Updcnt%m)) restart();

    return get_ans();
}

void init(int nn, int ll, int xs[]) {
	n=nn,l=ll;
	
	m=sqrt(n);
	m+=(m*m!=n);
	Ms=(n+m-1)/m;
	
	for (int i=0; i<n; i++) {
		A[i]=xs[i];
		v[i/m].push_back(A[i]);
	}
	
	for (int i=0; i<Ms; i++) 
		process_block(i);

    return;
}

Compilation message

elephants.cpp: In function 'void process_block(int)':
elephants.cpp:17:22: warning: unused variable 'rmax' [-Wunused-variable]
  int r=v[x].size()-1,rmax=v[x][v[x].size()-1];
                      ^~~~
elephants.cpp: In function 'int get_ans()':
elephants.cpp:40:6: warning: unused variable 'pos' [-Wunused-variable]
  int pos=v[cur_block][0],idx=0;
      ^~~
elephants.cpp: In function 'void restart()':
elephants.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0; j<v[i].size(); j++) 
                 ~^~~~~~~~~~~~
elephants.cpp:71:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int j=0; j<v[i].size(); j++) 
   ^~~
elephants.cpp:73:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
    v[i].clear();
    ^
elephants.cpp:76:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<h.size(); i++) 
                ~^~~~~~~~~
elephants.cpp: In function 'void del(int)':
elephants.cpp:91:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0; j<v[cur_block].size(); j++) 
                 ~^~~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void ins(int)':
elephants.cpp:111:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0; j<v[cur_block].size(); j++) 
                 ~^~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 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 504 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 632 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 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 632 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 367 ms 3348 KB Output is correct
8 Correct 463 ms 3864 KB Output is correct
9 Correct 682 ms 5932 KB Output is correct
10 Correct 632 ms 5508 KB Output is correct
11 Correct 550 ms 5584 KB Output is correct
12 Correct 920 ms 5780 KB Output is correct
13 Correct 666 ms 5408 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 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 632 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 367 ms 3348 KB Output is correct
8 Correct 463 ms 3864 KB Output is correct
9 Correct 682 ms 5932 KB Output is correct
10 Correct 632 ms 5508 KB Output is correct
11 Correct 550 ms 5584 KB Output is correct
12 Correct 920 ms 5780 KB Output is correct
13 Correct 666 ms 5408 KB Output is correct
14 Correct 463 ms 4756 KB Output is correct
15 Correct 783 ms 4740 KB Output is correct
16 Correct 1369 ms 6452 KB Output is correct
17 Correct 1611 ms 7824 KB Output is correct
18 Correct 1672 ms 7788 KB Output is correct
19 Correct 1172 ms 8008 KB Output is correct
20 Correct 1601 ms 7852 KB Output is correct
21 Correct 1597 ms 7804 KB Output is correct
22 Correct 1112 ms 7396 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 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 632 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 367 ms 3348 KB Output is correct
8 Correct 463 ms 3864 KB Output is correct
9 Correct 682 ms 5932 KB Output is correct
10 Correct 632 ms 5508 KB Output is correct
11 Correct 550 ms 5584 KB Output is correct
12 Correct 920 ms 5780 KB Output is correct
13 Correct 666 ms 5408 KB Output is correct
14 Correct 463 ms 4756 KB Output is correct
15 Correct 783 ms 4740 KB Output is correct
16 Correct 1369 ms 6452 KB Output is correct
17 Correct 1611 ms 7824 KB Output is correct
18 Correct 1672 ms 7788 KB Output is correct
19 Correct 1172 ms 8008 KB Output is correct
20 Correct 1601 ms 7852 KB Output is correct
21 Correct 1597 ms 7804 KB Output is correct
22 Correct 1112 ms 7396 KB Output is correct
23 Correct 4899 ms 14648 KB Output is correct
24 Correct 5084 ms 14648 KB Output is correct
25 Correct 4038 ms 14672 KB Output is correct
26 Correct 4384 ms 14824 KB Output is correct
27 Correct 4408 ms 14536 KB Output is correct
28 Correct 694 ms 5788 KB Output is correct
29 Correct 642 ms 5892 KB Output is correct
30 Correct 705 ms 5784 KB Output is correct
31 Correct 638 ms 5784 KB Output is correct
32 Correct 3812 ms 14020 KB Output is correct
33 Correct 2984 ms 13432 KB Output is correct
34 Correct 4126 ms 14316 KB Output is correct
35 Correct 2911 ms 14588 KB Output is correct
36 Correct 2188 ms 13996 KB Output is correct
37 Correct 4700 ms 15208 KB Output is correct
38 Correct 4457 ms 13356 KB Output is correct
39 Correct 4038 ms 14292 KB Output is correct
40 Correct 4441 ms 13320 KB Output is correct
41 Correct 5456 ms 14148 KB Output is correct
42 Correct 5468 ms 14240 KB Output is correct