oj.uz

Submission #352443

# Submission time Handle Problem Language Result Execution time Memory
352443 2021-01-20T18:54:24 Z minoum Dancing Elephants (IOI11_elephants) C++17
100 / 100
 8306 ms 14480 KB 
//#include "elephants.h"
#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;

const int MAXN = 15e4+1, sqr = 500;
int n, pos[MAXN], cnt = 0, seg[MAXN], l, last = 0;
vector <pair<int,int>> dp[sqr], pts;
vector <int> all[sqr], tmp;
//multiset <pair<int,int>> el;

void init(int N, int L, int X[]){
	n = N; l = L;
	for(int i = 0; i < n; i++){
		pos[i] = X[i];
	} 

}

void caldp(int ind){
	for(int i = 0; i < (int)all[ind].size(); i++) dp[ind].push_back({0,0});
	int id = (int)all[ind].size();
	for(int i = (int)all[ind].size()-1; i>=0; i--){
		//int id = upper_bound(all[ind].begin(), all[ind].end(), all[ind][i]+l) - all[ind].begin();
		while(id > 0 && all[ind][id-1] > all[ind][i]+l) id--;
		if(id >= (int)all[ind].size()){
			dp[ind][i].first = 1; dp[ind][i].second = all[ind][i]+l+1; 
			continue;
		}
		dp[ind][i].first = dp[ind][id].first+1; dp[ind][i].second = dp[ind][id].second;
	}
	return;
}

void build(){
//	cout << "build!!" << endl;
//	el.clear();
	pts.clear();
	for(int i = 0; i < n; i++) pts.push_back({pos[i], i});
	for(int i = 0; i < last; i++) all[i].clear(), dp[i].clear();
	sort(pts.begin(), pts.end());
	int pt = 0, c = 0;
	while(pt < n){
		while(pt < n && (int)all[c].size() < sqr){
			all[c].push_back(pts[pt].first);
			seg[pts[pt].second] = c; pt++;
		}
		caldp(c);
		c++;
	}
	last = c;
//	for(int i = 0; i < n; i++) el.insert({pos[i], seg[i]});
	return;
}

void del(int ind, int val){
	while(all[ind].back() != val){
		tmp.push_back(all[ind].back());
		all[ind].pop_back();
	}
	all[ind].pop_back();
	while(!tmp.empty()){
		all[ind].push_back(tmp.back());
		tmp.pop_back();
	}
	dp[ind].clear(); caldp(ind);
	return;
}

void add(int ind, int val){
	while(!all[ind].empty() && all[ind].back() > val){
		tmp.push_back(all[ind].back());
		all[ind].pop_back();
	}
	all[ind].push_back(val);
	while(!tmp.empty()){
		all[ind].push_back(tmp.back());
		tmp.pop_back();
	}
	dp[ind].clear(); caldp(ind);
	return; 
}

int get(){
	int cur = all[0][0], res = 0, pt = 0;
	while(pt < last){
		while(pt < last && cur > all[pt].back()) pt++;
		if(pt >= last) break;
		int ind = pt;
		int id = lower_bound(all[ind].begin(), all[ind].end(), cur) - all[ind].begin();
		res += dp[ind][id].first; cur = dp[ind][id].second;
	}
	return res;
}

int update(int i, int y){
	if(cnt % (sqr-3) == 0) build();
	del(seg[i],pos[i]);
	int pt = 0;
	while(pt+1 < last && y > all[pt+1][0]) pt++;
	add(pt, y);
	seg[i] = pt; pos[i] = y;
	int ans = get(); cnt++;
	return ans;
}

/*int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//	init(NN, L1, tof);
	cin >> n >> l;
	for(int i = 0; i < n; i++) cin >> pos[i];
	cout << update(2,16) << endl;
	cout << update(1,25) << endl;
	cout << update(3,35) << endl;
	cout << update(0,38) << endl;
	cout << update(2,0) << endl;
	return 0; 
}*/

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 384 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 384 KB Output is correct
7 Correct 859 ms 1428 KB Output is correct
8 Correct 889 ms 1640 KB Output is correct
9 Correct 891 ms 2696 KB Output is correct
10 Correct 889 ms 2532 KB Output is correct
11 Correct 856 ms 2660 KB Output is correct
12 Correct 1387 ms 2796 KB Output is correct
13 Correct 903 ms 2660 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 384 KB Output is correct
7 Correct 859 ms 1428 KB Output is correct
8 Correct 889 ms 1640 KB Output is correct
9 Correct 891 ms 2696 KB Output is correct
10 Correct 889 ms 2532 KB Output is correct
11 Correct 856 ms 2660 KB Output is correct
12 Correct 1387 ms 2796 KB Output is correct
13 Correct 903 ms 2660 KB Output is correct
14 Correct 913 ms 2024 KB Output is correct
15 Correct 1325 ms 2280 KB Output is correct
16 Correct 2131 ms 2868 KB Output is correct
17 Correct 2324 ms 3800 KB Output is correct
18 Correct 2480 ms 3680 KB Output is correct
19 Correct 1705 ms 3552 KB Output is correct
20 Correct 2328 ms 3680 KB Output is correct
21 Correct 2316 ms 4064 KB Output is correct
22 Correct 1495 ms 3552 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 384 KB Output is correct
7 Correct 859 ms 1428 KB Output is correct
8 Correct 889 ms 1640 KB Output is correct
9 Correct 891 ms 2696 KB Output is correct
10 Correct 889 ms 2532 KB Output is correct
11 Correct 856 ms 2660 KB Output is correct
12 Correct 1387 ms 2796 KB Output is correct
13 Correct 903 ms 2660 KB Output is correct
14 Correct 913 ms 2024 KB Output is correct
15 Correct 1325 ms 2280 KB Output is correct
16 Correct 2131 ms 2868 KB Output is correct
17 Correct 2324 ms 3800 KB Output is correct
18 Correct 2480 ms 3680 KB Output is correct
19 Correct 1705 ms 3552 KB Output is correct
20 Correct 2328 ms 3680 KB Output is correct
21 Correct 2316 ms 4064 KB Output is correct
22 Correct 1495 ms 3552 KB Output is correct
23 Correct 5186 ms 6940 KB Output is correct
24 Correct 5614 ms 11960 KB Output is correct
25 Correct 4694 ms 12144 KB Output is correct
26 Correct 6057 ms 11868 KB Output is correct
27 Correct 6797 ms 11824 KB Output is correct
28 Correct 2801 ms 5356 KB Output is correct
29 Correct 2743 ms 5356 KB Output is correct
30 Correct 2804 ms 5356 KB Output is correct
31 Correct 2751 ms 5312 KB Output is correct
32 Correct 4981 ms 11356 KB Output is correct
33 Correct 4848 ms 10716 KB Output is correct
34 Correct 5238 ms 11484 KB Output is correct
35 Correct 5290 ms 14480 KB Output is correct
36 Correct 3936 ms 11356 KB Output is correct
37 Correct 7950 ms 14300 KB Output is correct
38 Correct 5156 ms 10588 KB Output is correct
39 Correct 5692 ms 11612 KB Output is correct
40 Correct 5357 ms 10588 KB Output is correct
41 Correct 8148 ms 11612 KB Output is correct
42 Correct 8306 ms 11996 KB Output is correct