oj.uz

Submission #558821

# Submission time Handle Problem Language Result Execution time Memory
558821 2022-05-08T13:47:42 Z mosiashvililuka Dancing Elephants (IOI11_elephants) C++14
100 / 100
 5736 ms 16256 KB 
#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
int T=300,B=150000/T+3;
int a,b,c,d,e,i,j,ii,jj,zx,xc,L,lef,rig,mid,k[150009],f[150009],C,D,cnt,II,JJ,pas;
vector <int> v[150009],vv;
vector <pair <int, int> > dp[150009];
void REBL(int q){
	int lef,rig,mid,h=q,hh;
	dp[h].resize(v[h].size());
	if(v[h].size()==0) return;
	for(hh=v[h].size()-1; hh>=0; hh--){
		lef=hh;rig=v[h].size();
		while(lef+1<rig){
			mid=((lef+rig)>>1);
			if(v[h][mid]>v[h][hh]+L){
				rig=mid;
			}else{
				lef=mid;
			}
		}
		if(rig==v[h].size()){
			dp[h][hh]={1,v[h][hh]+L};
		}else{
			dp[h][hh]=dp[h][rig];dp[h][hh].first++;
		}
	}
}
void REDO(){
	int lef,rig,mid;
	int h=0,hh=0,qw=0;vv.clear();
	for(h=1; h<=B; h++){
		for(hh=0; hh<v[h].size(); hh++){
			vv.push_back(v[h][hh]);
		}
		v[h].clear();
	}
	qw=0;
	for(h=0; h<vv.size(); h++){
		if(h%T==0) qw++;
		v[qw].push_back(vv[h]);
	}
	for(h=1; h<=B; h++){
		k[h]=k[h-1];
		if(v[h].size()==0) continue;
		k[h]=v[h][v[h].size()-1];
		REBL(h);
	}
	k[B]=1000000003;
}
void init(int NN, int LL, int XX[]){
	a=NN;L=LL;
	for(i=1; i<=a; i++){
		v[1].push_back(XX[i-1]);
		f[i]=XX[i-1];
	}
	REDO();
}
int fnd(int q){
	int lef,rig,mid;
	lef=0;rig=B+1;
	while(lef+1<rig){
		mid=((lef+rig)>>1);
		if(k[mid]>=q){
			rig=mid;
		}else{
			lef=mid;
		}
	}
	return rig;
}
int fndbl(int q, int w){
	int lef,rig,mid;
	lef=-1;rig=v[q].size();
	while(lef+1<rig){
		mid=((lef+rig)>>1);
		if(v[q][mid]>=w){
			rig=mid;
		}else{
			lef=mid;
		}
	}
	return rig;
}
int update(int Ii, int Yy){
	int h,hh;
	Ii++;
	i=Ii;D=Yy;C=f[i];cnt++;
	ii=fnd(C);e=0;
	if(k[ii]==C){
		if(v[ii].size()==0||v[ii][v[ii].size()-1]!=C){
			ii++;II=0;e=1;
		}
	}
	if(e==0){
		II=fndbl(ii,C);
	}
	v[ii].erase(v[ii].begin()+II);
	
	jj=fnd(D);
	JJ=fndbl(jj,D);
	v[jj].insert(v[jj].begin()+JJ,D);
	
	REBL(ii);REBL(jj);
	if(cnt%T==0) REDO();
	f[i]=D;
	
	II=-2;pas=0;
	for(h=1; h<=B; h++){
		if(v[h].size()==0) continue;
		c=fndbl(h,II+1);
		if(c==v[h].size()){
			continue;
		}
		pas+=dp[h][c].first;II=dp[h][c].second;
	}
	return pas;
}

Compilation message

elephants.cpp: In function 'void REBL(int)':
elephants.cpp:22:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   if(rig==v[h].size()){
      |      ~~~^~~~~~~~~~~~~
elephants.cpp: In function 'void REDO()':
elephants.cpp:33:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   for(hh=0; hh<v[h].size(); hh++){
      |             ~~^~~~~~~~~~~~
elephants.cpp:39:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(h=0; h<vv.size(); h++){
      |           ~^~~~~~~~~~
elephants.cpp:30:6: warning: unused variable 'lef' [-Wunused-variable]
   30 |  int lef,rig,mid;
      |      ^~~
elephants.cpp:30:10: warning: unused variable 'rig' [-Wunused-variable]
   30 |  int lef,rig,mid;
      |          ^~~
elephants.cpp:30:14: warning: unused variable 'mid' [-Wunused-variable]
   30 |  int lef,rig,mid;
      |              ^~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:112:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |   if(c==v[h].size()){
      |      ~^~~~~~~~~~~~~
elephants.cpp:86:8: warning: unused variable 'hh' [-Wunused-variable]
   86 |  int h,hh;
      |        ^~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 511 ms 8516 KB Output is correct
8 Correct 530 ms 8532 KB Output is correct
9 Correct 570 ms 9672 KB Output is correct
10 Correct 640 ms 9488 KB Output is correct
11 Correct 630 ms 9496 KB Output is correct
12 Correct 818 ms 9904 KB Output is correct
13 Correct 930 ms 9548 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 511 ms 8516 KB Output is correct
8 Correct 530 ms 8532 KB Output is correct
9 Correct 570 ms 9672 KB Output is correct
10 Correct 640 ms 9488 KB Output is correct
11 Correct 630 ms 9496 KB Output is correct
12 Correct 818 ms 9904 KB Output is correct
13 Correct 930 ms 9548 KB Output is correct
14 Correct 738 ms 9020 KB Output is correct
15 Correct 833 ms 9048 KB Output is correct
16 Correct 1310 ms 10224 KB Output is correct
17 Correct 1363 ms 10944 KB Output is correct
18 Correct 1585 ms 10996 KB Output is correct
19 Correct 1116 ms 10328 KB Output is correct
20 Correct 1356 ms 11008 KB Output is correct
21 Correct 1379 ms 11152 KB Output is correct
22 Correct 1581 ms 10360 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 511 ms 8516 KB Output is correct
8 Correct 530 ms 8532 KB Output is correct
9 Correct 570 ms 9672 KB Output is correct
10 Correct 640 ms 9488 KB Output is correct
11 Correct 630 ms 9496 KB Output is correct
12 Correct 818 ms 9904 KB Output is correct
13 Correct 930 ms 9548 KB Output is correct
14 Correct 738 ms 9020 KB Output is correct
15 Correct 833 ms 9048 KB Output is correct
16 Correct 1310 ms 10224 KB Output is correct
17 Correct 1363 ms 10944 KB Output is correct
18 Correct 1585 ms 10996 KB Output is correct
19 Correct 1116 ms 10328 KB Output is correct
20 Correct 1356 ms 11008 KB Output is correct
21 Correct 1379 ms 11152 KB Output is correct
22 Correct 1581 ms 10360 KB Output is correct
23 Correct 4254 ms 14780 KB Output is correct
24 Correct 4533 ms 14784 KB Output is correct
25 Correct 3338 ms 14700 KB Output is correct
26 Correct 3964 ms 13700 KB Output is correct
27 Correct 4904 ms 13684 KB Output is correct
28 Correct 2697 ms 9316 KB Output is correct
29 Correct 2701 ms 9340 KB Output is correct
30 Correct 2741 ms 9368 KB Output is correct
31 Correct 2684 ms 9316 KB Output is correct
32 Correct 4194 ms 13796 KB Output is correct
33 Correct 3493 ms 13688 KB Output is correct
34 Correct 4107 ms 13692 KB Output is correct
35 Correct 4315 ms 16256 KB Output is correct
36 Correct 5162 ms 13680 KB Output is correct
37 Correct 3816 ms 15368 KB Output is correct
38 Correct 5736 ms 13692 KB Output is correct
39 Correct 3715 ms 13692 KB Output is correct
40 Correct 5588 ms 13688 KB Output is correct
41 Correct 4744 ms 15096 KB Output is correct
42 Correct 4787 ms 15048 KB Output is correct