oj.uz

Submission #416020

# Submission time Handle Problem Language Result Execution time Memory
416020 2021-06-01T20:06:15 Z CSQ31 Dancing Elephants (IOI11_elephants) C++14
100 / 100
 3687 ms 13720 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
typedef long long int ll;
typedef vector<vector<int>> vii;
typedef pair<int,int> pii;
int n,l;
int x[1500001];
int blk = 500;
struct bucket{
	int sz;
	int x[1001];
	int cnt[1001];
	int reach[1001];
	void calc(){
		int t = sz;
		for(int i=sz-1;i>=0;i--){
			while(t && x[t-1] > x[i]+l)t--;
			if(t == sz){
				cnt[i] = 1;
				reach[i] = x[i]+l;
			}else{
				cnt[i] = cnt[t]+1;
				reach[i] = reach[t];
				
			}
		}
		
	}
	void add(int y){
		int p = ub(x,x+sz,y) - x;
		sz++;
		for(int i=sz-1;i>p;i--)x[i] = x[i-1];
		x[p] = y;
		calc();
	}
	void del(int y){
		int p = lb(x,x+sz,y) - x;
		sz--;
		for(int i=p;i<sz;i++)x[i] = x[i+1];
		calc();
		
	}
	
}b[500];
int bcnt = 0;
void init(int N, int L, int X[])
{
	n = N;
	l = L;
	for(int i=0;i<n;i++)x[i] = X[i];
	for(int i=0;i<n;i+=blk){
		for(int j=i;j<min(i+blk,n);j++){
			b[bcnt].x[b[bcnt].sz++] = x[j];
		}
		b[bcnt++].calc();
	}
	//for(int i=0;i<n;i++)cout<<b[0].x[i]<<" "<<b[0].cnt[i]<<" "<<b[0].reach[i]<<'\n';
//cout<<"BUILT"<<'\n';
}
void rebuild(){
	vector<int>nx;
	for(int i=0;i<bcnt;i++){
		for(int j=0;j<b[i].sz;j++){
			nx.pb(b[i].x[j]);
		}
	}
	bcnt = 0;
	for(int i=0;i<n;i+=blk){
		b[bcnt].sz = 0;
		for(int j=i;j<min(i+blk,n);j++){
			b[bcnt].x[b[bcnt].sz++] = nx[j];
		}
		b[bcnt++].calc();
	}
}
int num = 0;
int update(int i, int y)
{
	if(num == 400){rebuild();num=0;}
	int pv = x[i];
	//cout<<"del"<<'\n';
	for(int i=0;i<bcnt;i++){
		if(b[i].x[0] <= pv && b[i].x[b[i].sz-1] >= pv){
			b[i].del(pv);
			break;
		}
	}
	//for(int i=0;i<n;i++)cout<<b[0].x[i]<<" "<<b[0].cnt[i]<<" "<<b[0].reach[i]<<'\n';
	x[i] = y;
	for(int i=0;i<bcnt;i++){
		if((i == 0 || b[i].x[0] <= y) && (i == bcnt-1 || (b[i+1].x[0] > y))){
			b[i].add(y);
			break;
		}
	}
	//if(num == 2){
		//cout<<b[0].sz<<'\n';
		//for(int i=0;i<n;i++)cout<<b[0].x[i]<<" "<<b[0].cnt[i]<<" "<<b[0].reach[i]<<'\n';
	//}
	int ans = 0;
	int cur = -1;
	for(int i=0;i<bcnt;i++){
		if(cur>=b[i].x[b[i].sz-1])continue;
		if(cur < b[i].x[0]){
			ans+=b[i].cnt[0];
			cur = b[i].reach[0];
			continue;
		}
		int p = ub(b[i].x,b[i].x+b[i].sz,cur) - b[i].x;
		ans+=b[i].cnt[p];
		cur=b[i].reach[p];
	}
	num++;
	return ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 452 ms 2312 KB Output is correct
8 Correct 497 ms 2740 KB Output is correct
9 Correct 346 ms 4732 KB Output is correct
10 Correct 419 ms 4348 KB Output is correct
11 Correct 356 ms 4416 KB Output is correct
12 Correct 691 ms 4448 KB Output is correct
13 Correct 449 ms 4068 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 452 ms 2312 KB Output is correct
8 Correct 497 ms 2740 KB Output is correct
9 Correct 346 ms 4732 KB Output is correct
10 Correct 419 ms 4348 KB Output is correct
11 Correct 356 ms 4416 KB Output is correct
12 Correct 691 ms 4448 KB Output is correct
13 Correct 449 ms 4068 KB Output is correct
14 Correct 363 ms 3384 KB Output is correct
15 Correct 692 ms 3508 KB Output is correct
16 Correct 1087 ms 5024 KB Output is correct
17 Correct 1069 ms 6236 KB Output is correct
18 Correct 1285 ms 6112 KB Output is correct
19 Correct 756 ms 6432 KB Output is correct
20 Correct 1058 ms 6156 KB Output is correct
21 Correct 1085 ms 6320 KB Output is correct
22 Correct 783 ms 5744 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 452 ms 2312 KB Output is correct
8 Correct 497 ms 2740 KB Output is correct
9 Correct 346 ms 4732 KB Output is correct
10 Correct 419 ms 4348 KB Output is correct
11 Correct 356 ms 4416 KB Output is correct
12 Correct 691 ms 4448 KB Output is correct
13 Correct 449 ms 4068 KB Output is correct
14 Correct 363 ms 3384 KB Output is correct
15 Correct 692 ms 3508 KB Output is correct
16 Correct 1087 ms 5024 KB Output is correct
17 Correct 1069 ms 6236 KB Output is correct
18 Correct 1285 ms 6112 KB Output is correct
19 Correct 756 ms 6432 KB Output is correct
20 Correct 1058 ms 6156 KB Output is correct
21 Correct 1085 ms 6320 KB Output is correct
22 Correct 783 ms 5744 KB Output is correct
23 Correct 2890 ms 13720 KB Output is correct
24 Correct 3273 ms 13556 KB Output is correct
25 Correct 1993 ms 13704 KB Output is correct
26 Correct 3560 ms 13688 KB Output is correct
27 Correct 3082 ms 13464 KB Output is correct
28 Correct 1743 ms 5200 KB Output is correct
29 Correct 1679 ms 5204 KB Output is correct
30 Correct 1731 ms 5204 KB Output is correct
31 Correct 1762 ms 5220 KB Output is correct
32 Correct 2003 ms 13104 KB Output is correct
33 Correct 1753 ms 12264 KB Output is correct
34 Correct 2368 ms 13184 KB Output is correct
35 Correct 1723 ms 13548 KB Output is correct
36 Correct 1628 ms 12940 KB Output is correct
37 Correct 2627 ms 13468 KB Output is correct
38 Correct 2883 ms 12204 KB Output is correct
39 Correct 2979 ms 13104 KB Output is correct
40 Correct 3248 ms 12456 KB Output is correct
41 Correct 3687 ms 12904 KB Output is correct
42 Correct 3597 ms 13252 KB Output is correct