Submission #352441

#	Time	Username	Problem	Language	Result	Execution time	Memory
352441		minoum	Dancing Elephants (IOI11_elephants)	C++17	97 / 100	9026 ms	8412 KiB

elephants

//#include "elephants.h"
#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;

const int MAXN = 15e4+1, sqr = 550;
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});
	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();
		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 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 0 / 3