제출 #352423

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
352423		minoum	코끼리 (Dancing Elephants) (IOI11_elephants)	C++17	50 / 100	9021 ms	10040 KiB

elephants

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

using namespace std;
typedef long long int ll;

const int MAXN = 15e4+5, sqr = 390;
int n, pos[MAXN], cnt = 0, seg[MAXN], l;
vector <pair<int,int>> dp[sqr];
vector <int> all[sqr];
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];
		//el.insert({pos[i], 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();
	vector <pair<int,int>> pts;
	for(int i = 0; i < n; i++) pts.push_back({pos[i], i});
	for(int i = 0; i < sqr; 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++;
	}
	for(int i = 0; i < n; i++) el.insert({pos[i], seg[i]});
	return;
}

void del(int ind, int val){
	vector <int> tmp;
	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){
	vector <int> tmp;
	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 = el.begin()->first, res = 0;
	while(cur <= el.rbegin()->first){
		int ind = el.lower_bound({cur,0})->second;
		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 % 380 == 0) build();
	del(seg[i],pos[i]);
	auto it = el.lower_bound({pos[i],seg[i]});
	el.erase(it);
	int pt = el.rbegin()->second;
	it = el.lower_bound({y,0});
	if(it != el.end()) pt = it->second;
	add(pt, y); el.insert({y, pt});
	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: 0 / 47
• Subtask 5: 0 / 3