oj.uz

답안 #752533

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
752533 2023-06-03T06:56:50 Z minhcool 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
50 / 100
 9000 ms 13840 KB 
#include "elephants.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
#define ll long long
#define fi first
#define se second
#define pb push_back
//#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, ii> iii;
typedef pair<ii, ii> iiii;
 
const int N = 4e5 + 5;
 
const int oo = 1e9 + 7, mod = 1e9 + 7;
 
mt19937 rng(1);
 
ll rnd(ll l, ll r){
	ll temp = rng() % (r - l + 1);
	return abs(temp) + l;
}
 
struct cmp{
	bool operator()(const ii& a, const ii& b){
		return a.fi < b.fi;
	}
};
 
set<ii> mls;
 
vector<ii> vc1, vc2;
 
int n, l, arr[N];
 
int nxt[N][21];
 
double total = 0;
 
int lst_ans, temp;
 
bool ok[N];
 
void rebuild(){
	clock_t c1 = clock(), c2;
	arr[n] = oo;
	vector<ii> v;
//	for(int i = 0; i <= n; i++) v.pb({arr[i], i});
//	sort(v.begin(), v.end());
	set<ii>::iterator itr = mls.begin();
	vc1.clear();
	for(auto it : mls){
		//cout << arr[i] + l + 1 << "\n";
		while(itr != mls.end() && ((*itr).fi <= (it.fi + l))) itr++;
		//vector<ii>::iterator it = lower_bound(v.begin(), v.end(), make_pair(arr[i] + l + 1, -oo));
		//nxt[i][0] = (it == v.end() ? make_pair(oo, n) : (*it));
	//	cout << (itr == mls.end()) << "\n";
		nxt[it.se][0] = (itr == mls.end() ? n : (*itr).se);
	//	cout << it.fi << " " << it.se << " " << nxt[it.se][0].fi << " " << nxt[it.se][1].se << "\n";
		//cout << nxt[i][0].fi << " " << nxt[i][0].se << "\n";
		vc1.pb(it);
	}
//	sort(vc1.begin(), vc1.end());// take long
	vc2.clear();
	nxt[n][0] = n;
	for(int i = 0; i <= n; i++) ok[i] = 1;
	temp = 8;
	for(int i = 1; i <= temp; i++){
		for(int j = 0; j <= n; j++){
			nxt[j][i] = nxt[nxt[j][i - 1]][i - 1];
			//cout << i << " " << j << " " << nxt[j][i].fi << " " << nxt[j][i].se << "\n";
		}
	}
	c2 = clock();
	total += (double)(c2 - c1) / (double)CLOCKS_PER_SEC;
}
 
int counter = 0;
 
set<int> poss;
 
unordered_set<int> ins;
gp_hash_table<int, int> mp1, mp2, mp3;
 
gp_hash_table<int, set<int>> tempo;
 
bool all(int pos){
	return (mp1[pos] == mp2[pos]);
}
 
void init(int N, int L, int X[]){
	n = N, l = L;
	for(ll i = 0; i < n; i++) arr[i] = X[i];
	for(ll i = 0; i < n; i++) mls.insert({arr[i], i});
	for(int i = 0; i < n; i++) mp1[arr[i]]++;
	rebuild();
	poss.insert(-1), poss.insert(1e9 + 1);
}
 
int cnt = 0;
int update(int i, int y){
	counter++;
	mls.erase({arr[i], i});
	ok[i] = 0;
	mp1[arr[i]]--;
	if(ins.find(i) != ins.end()) mp2[arr[i]]--;
	poss.insert(arr[i]); 
	arr[i] = y;
	ins.insert(arr[i]);
	mp2[arr[i]]++;
	poss.insert(arr[i]);
	mp1[arr[i]]++;
	mls.insert({arr[i], i});
	vector<ii> vc3;
	bool ckk = 0;
	for(auto it2 : vc2){
		if(it2.fi >= arr[i] && !ckk){
			ckk = 1;
			vc3.pb({arr[i], i});
		}
		vc3.pb(it2);
	}
	if(!ckk) vc3.pb({arr[i], i});
	vc2 = vc3;
//	sort(vc2.begin(), vc2.end());//take long
	//for(auto it : vc1) if(it.fi <= 2000) cout << 1 << " " << it.fi << " " << it.se << " " << arr[it.se] << "\n";
	//for(auto it : vc2) if(it.fi <= 2000) cout << 2 << " " << it.fi << " " << it.se << " " << arr[it.se] << "\n";
	/*
	int ans = 0, lst = -1;
	for(auto it : mls){
		if(lst > it) continue;
		ans++;
		lst = it + l;
	}*/
	int ans = 0;
	int lst = -1;
	bool ck = 1;
	vector<ii>::iterator it3 = vc2.begin(), it4;
	for(auto itt : poss){
		int it = itt;
	//	cout << counter << " " << it << " " << lst << " " << arr[lst] << " " << ans << " " << all(arr[lst]) <<  "\n";
		//cout << ans << " " << lst << "\n";
		if(lst < 0){
			set<ii>::iterator it2;
			if(mp2[it] && (it > (-oo + l))){
				ans++;
				it2 = mls.lower_bound({-oo + l + 1, -oo});
				if(it2 == mls.end()) break;
				lst = (*it2).se;
				//lst = it;
			}
			else{
				it2 = mls.lower_bound({-oo + l + 1, -oo});
				if(it2 == mls.end()) break;
				ans++;
				lst = (*it2).se;
			}
		}
		else if(all(arr[lst])){
		//	set<ii>::iterator it4 = mls.lower_bound({arr[lst] + l + 1, -oo});
			int target = arr[lst] + l + 1;
			vector<ii>::iterator it2 = lower_bound(vc1.begin(), vc1.end(), make_pair(target, -oo));
	//		cout << (*it2).fi << " " << (*it2).se << "\n";
			while(it2 != vc1.end() && arr[(*it2).se] != (*it2).fi) it2++;
//			it3 = lower_bound(vc2.begin(), vc2.end(), make_pair(arr[lst] + l + 1, -oo));
			while(it3 != vc2.end() && (*it3).fi < target) it3++;
			while(it3 != vc2.end() && arr[(*it3).se] != (*it3).fi) it3++;
			ii mn = {oo, oo};
			if(it2 != vc1.end()) mn = (*it2);
			if(it3 != vc2.end()) mn = min(mn, (*it3));
	//		cout << "OK " << mn.fi << " " << (*it4).fi << "\n";
		//	assert(mn.fi <= (*it4).fi);
			if(mn.fi == oo) break;
			//if(it2 == mls.end()) break;
			lst = mn.se;
			ans++;
			it4 = it3;
				while(it2 != vc1.end() && !ok[(*it2).se]) it2++;
				if(it2 != vc1.end() && (*it2).fi == mn.fi) lst = (*it2).se;
				while(it3 != vc2.end() && !ok[(*it3).se]) it3++;
				if(it3 != vc2.end() && (*it3).fi == mn.fi) lst = (*it3).se;
				it3 = it4;
		//	cout << "OK3 " << ans << " " << lst << "\n";
		}
		else{
			for(int ii = temp; ii >= 0; ii--){
			//	cout << i << " " << nxt[lst][i].fi << " " << nxt[lst][i].se << " " << it << "\n";
			//	if(nxt[lst][i].fi >= it) continue;
				//if(!ck) continue;
		//		cout << "OKAY " << lst << " " << arr[lst] << "\n";
				int temp = nxt[lst][ii];
				while(ok[temp] && arr[temp] < it){
					ans += (1 << ii);
				//	assert(arr[nxt[lst][i].se] == nxt[lst][i].fi);
					lst = temp;
					temp = nxt[lst][ii];
		//			cout << lst << " " << arr[lst] << " " << ans << "\n";
				}
				//cout << lst << " " << ans << "\n";
			}
		//	cout << counter << " " << lst << " " << ans << "\n";
		//cout << ans << " " << lst << " " << arr[lst] << " " << it << "\n";
			//set<ii>::iterator it2 = mls.lower_bound({it, -oo});
			//cout << arr[lst] + l << " " << ans << "\n";
//			set<ii>::iterator it2;
			if(mp1[it] && (it > (arr[lst] + l))){
				ans++;
				int target = it + l + 1;
		//		set<ii>::iterator it4 = mls.lower_bound({it + l + 1, -oo});
			//	cout << it + l + 1 << " " << vc1.back().fi << " " << vc2.back().fi << "\n";
				vector<ii>::iterator it2 = lower_bound(vc1.begin(), vc1.end(), make_pair(target, -oo));
		//		cout << "WTF " << (*it2).fi << " " << (*it2).se << "\n";
				while(it2 != vc1.end() && arr[(*it2).se] != (*it2).fi) it2++;
		//		it3 = lower_bound(vc2.begin(), vc2.end(), make_pair(it + l + 1, -oo));
				while(it3 != vc2.end() && (*it3).fi < target) it3++;
				while(it3 != vc2.end() && arr[(*it3).se] != (*it3).fi) it3++;
				ii mn = {oo, oo};
				if(it2 != vc1.end()) mn = (*it2);
				if(it3 != vc2.end()) mn = min(mn, (*it3));
		//		cout  << "OK " << mn.fi << " " << (*it4).fi << "\n";
			//	assert((*it4).fi >= mn.fi);
			//	cout << it + l + 1 << " " << (it2 == mls.end()) << "\n";
				if(mn.fi == oo) break;
				ans++;
				//cout << "OK " << it << " " << it + l + 1 << " " << (*it2).se << "\n";
				lst = mn.se;
				it4 = it3;
				while(it2 != vc1.end() && !ok[(*it2).se]) it2++;
				if(it2 != vc1.end() && (*it2).fi == mn.fi) lst = (*it2).se;
				while(it3 != vc2.end() && !ok[(*it3).se]) it3++;
				if(it3 != vc2.end() && (*it3).fi == mn.fi) lst = (*it3).se;
				it3 = it4;
			//	cout << "OK1 " << ans << " " << lst << "\n";
				//lst = it;
			}
			else{
				int target = arr[lst] + l + 1;
		//		cout << "OKAY\n";
		//		set<ii>::iterator it4 = mls.lower_bound({arr[lst] + l + 1, -oo});
				vector<ii>::iterator it2 = lower_bound(vc1.begin(), vc1.end(), make_pair(target, -oo));	
			//	cout << (*it2).fi << " " << (*it2).se << "\n";
				while(it2 != vc1.end() && arr[(*it2).se] != (*it2).fi) it2++;
				while(it3 != vc2.end() && (*it3).fi < target) it3++;
		//		it3 = lower_bound(vc2.begin(), vc2.end(), make_pair(arr[lst] + l + 1, -oo));
				while(it3 != vc2.end() && arr[(*it3).se] != (*it3).fi) it3++;
				ii mn = {oo, oo};
				if(it2 != vc1.end()) mn = (*it2);
				if(it3 != vc2.end()) mn = min(mn, (*it3));
		//		cout << "OK " << mn.fi << " " << (*it4).fi << "\n";
			//	cout << it + l + 1 << " " << (it2 == mls.end()) << "\n";
			//	assert((*it4).fi <= mn.fi);
				if(mn.fi == oo) break;
				ans++;
			//	cout << mn.se << "\n";
				lst = mn.se;
				it4 = it3;
				//cout << "OK " << it << " " << it + l + 1 << " " << (*it2).se << "\n";
				while(it2 != vc1.end() && !ok[(*it2).se]) it2++;
				if(it2 != vc1.end() && (*it2).fi == mn.fi) lst = (*it2).se;
				while(it3 != vc2.end() && !ok[(*it3).se]) it3++;
				if(it3 != vc2.end() && (*it3).fi == mn.fi) lst = (*it3).se;
				it3 = it4;
			//	cout << mn.se << "\n";
			//	cout << "OK2 " << ans << " " << lst << "\n";
			}
		//	cout << it << " " << ans << "\n";
			//cout << lst << "\n";
		}
		ck = 1;
	}
	///cnt++;
	//if(!(cnt % 1000)) cout << cnt << " " << "OK " << total << " " << (double)clock() / (double)CLOCKS_PER_SEC << "\n";
	if(!(counter % 20)){
		lst_ans = ans;
		poss.clear();
		mp2.clear();
		ins.clear();
		rebuild();
		poss.insert(-1), poss.insert(1e9 + 1);
	}
	//cout << ans << "\n";
	return ans;
}
 
/*
void process(){
 
}
 
signed main()
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll t;
	cin >> t;
	while(t--) process();
}
*/

Compilation message

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:141:7: warning: variable 'ck' set but not used [-Wunused-but-set-variable]
  141 |  bool ck = 1;
      |       ^~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1338 ms 5188 KB Output is correct
8 Correct 1791 ms 6308 KB Output is correct
9 Correct 4947 ms 13604 KB Output is correct
10 Correct 5451 ms 13608 KB Output is correct
11 Correct 7436 ms 13604 KB Output is correct
12 Correct 7219 ms 13604 KB Output is correct
13 Correct 4315 ms 13616 KB Output is correct

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1338 ms 5188 KB Output is correct
8 Correct 1791 ms 6308 KB Output is correct
9 Correct 4947 ms 13604 KB Output is correct
10 Correct 5451 ms 13608 KB Output is correct
11 Correct 7436 ms 13604 KB Output is correct
12 Correct 7219 ms 13604 KB Output is correct
13 Correct 4315 ms 13616 KB Output is correct
14 Correct 2450 ms 6540 KB Output is correct
15 Correct 3005 ms 9824 KB Output is correct
16 Execution timed out 9100 ms 13840 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1338 ms 5188 KB Output is correct
8 Correct 1791 ms 6308 KB Output is correct
9 Correct 4947 ms 13604 KB Output is correct
10 Correct 5451 ms 13608 KB Output is correct
11 Correct 7436 ms 13604 KB Output is correct
12 Correct 7219 ms 13604 KB Output is correct
13 Correct 4315 ms 13616 KB Output is correct
14 Correct 2450 ms 6540 KB Output is correct
15 Correct 3005 ms 9824 KB Output is correct
16 Execution timed out 9100 ms 13840 KB Time limit exceeded
17 Halted 0 ms 0 KB -