oj.uz

Submission #752541

# Submission time Handle Problem Language Result Execution time Memory
752541 2023-06-03T07:10:01 Z minhcool Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 32360 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]);
}

int ques;
 
void init(int N, int L, int X[]){
	if(N <= 50000) ques = 20;
	else ques = 70;
	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((total * 2) < (double)clock() / (double)CLOCKS_PER_SEC) ques = 20;
		else ques = 70;
	}
	if(!(counter % ques)){
		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:145:7: warning: variable 'ck' set but not used [-Wunused-but-set-variable]
  145 |  bool ck = 1;
      |       ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 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 882 ms 5192 KB Output is correct
8 Correct 963 ms 6048 KB Output is correct
9 Correct 1742 ms 13348 KB Output is correct
10 Correct 2683 ms 13472 KB Output is correct
11 Correct 8399 ms 13356 KB Output is correct
12 Correct 3034 ms 13352 KB Output is correct
13 Correct 1657 ms 13352 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 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 882 ms 5192 KB Output is correct
8 Correct 963 ms 6048 KB Output is correct
9 Correct 1742 ms 13348 KB Output is correct
10 Correct 2683 ms 13472 KB Output is correct
11 Correct 8399 ms 13356 KB Output is correct
12 Correct 3034 ms 13352 KB Output is correct
13 Correct 1657 ms 13352 KB Output is correct
14 Correct 1193 ms 6288 KB Output is correct
15 Correct 1602 ms 9444 KB Output is correct
16 Correct 4607 ms 13592 KB Output is correct
17 Correct 6122 ms 21884 KB Output is correct
18 Correct 6680 ms 21888 KB Output is correct
19 Correct 3803 ms 21888 KB Output is correct
20 Correct 6670 ms 21880 KB Output is correct
21 Correct 7229 ms 21880 KB Output is correct
22 Correct 3511 ms 21876 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 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 882 ms 5192 KB Output is correct
8 Correct 963 ms 6048 KB Output is correct
9 Correct 1742 ms 13348 KB Output is correct
10 Correct 2683 ms 13472 KB Output is correct
11 Correct 8399 ms 13356 KB Output is correct
12 Correct 3034 ms 13352 KB Output is correct
13 Correct 1657 ms 13352 KB Output is correct
14 Correct 1193 ms 6288 KB Output is correct
15 Correct 1602 ms 9444 KB Output is correct
16 Correct 4607 ms 13592 KB Output is correct
17 Correct 6122 ms 21884 KB Output is correct
18 Correct 6680 ms 21888 KB Output is correct
19 Correct 3803 ms 21888 KB Output is correct
20 Correct 6670 ms 21880 KB Output is correct
21 Correct 7229 ms 21880 KB Output is correct
22 Correct 3511 ms 21876 KB Output is correct
23 Execution timed out 9061 ms 32360 KB Time limit exceeded
24 Halted 0 ms 0 KB -