제출 #352427

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
352427		minoum	코끼리 (Dancing Elephants) (IOI11_elephants)	C++17	50 / 100	9061 ms	7480 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, last = 0;
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 < 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){
	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 % 387 == 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;
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3