oj.uz

Submission #752540

# Submission time Handle Problem Language Result Execution time Memory
752540 2023-06-03T07:04:55 Z minhcool Dancing Elephants (IOI11_elephants) C++17
50 / 100
 9000 ms 13592 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(!(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 0 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 0 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 0 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 1163 ms 5188 KB Output is correct
8 Correct 1549 ms 6052 KB Output is correct
9 Correct 4228 ms 13356 KB Output is correct
10 Correct 4766 ms 13352 KB Output is correct
11 Correct 7225 ms 13344 KB Output is correct
12 Correct 7209 ms 13352 KB Output is correct
13 Correct 3982 ms 13380 KB Output is correct

Subtask #4
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 0 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 1163 ms 5188 KB Output is correct
8 Correct 1549 ms 6052 KB Output is correct
9 Correct 4228 ms 13356 KB Output is correct
10 Correct 4766 ms 13352 KB Output is correct
11 Correct 7225 ms 13344 KB Output is correct
12 Correct 7209 ms 13352 KB Output is correct
13 Correct 3982 ms 13380 KB Output is correct
14 Correct 2327 ms 6288 KB Output is correct
15 Correct 2937 ms 9568 KB Output is correct
16 Execution timed out 9085 ms 13592 KB Time limit exceeded
17 Halted 0 ms 0 KB -

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 0 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 1163 ms 5188 KB Output is correct
8 Correct 1549 ms 6052 KB Output is correct
9 Correct 4228 ms 13356 KB Output is correct
10 Correct 4766 ms 13352 KB Output is correct
11 Correct 7225 ms 13344 KB Output is correct
12 Correct 7209 ms 13352 KB Output is correct
13 Correct 3982 ms 13380 KB Output is correct
14 Correct 2327 ms 6288 KB Output is correct
15 Correct 2937 ms 9568 KB Output is correct
16 Execution timed out 9085 ms 13592 KB Time limit exceeded
17 Halted 0 ms 0 KB -