oj.uz

Submission #752428

# Submission time Handle Problem Language Result Execution time Memory
752428 2023-06-03T03:02:40 Z minhcool Dancing Elephants (IOI11_elephants) C++17
26 / 100
 9000 ms 17416 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 = 2e5 + 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];
 
pair<int, int> nxt[N][21];
 
double total = 0;
 
int lst_ans, temp;
 
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() ? make_pair(oo, n) : (*itr));
	//	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] = {oo, n};
	temp = log2(n / max(1, lst_ans) + 1);
	for(int i = 1; i <= temp; i++){
		for(int j = 0; j <= n; j++){
			nxt[j][i] = nxt[nxt[j][i - 1].se][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});
	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();
	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;
			ans++;
			lst = mn.se;
		}
		else{
			for(int i = temp; i >= 0; i--){
			//	cout << i << " " << nxt[lst][i].fi << " " << nxt[lst][i].se << " " << it << "\n";
			//	if(nxt[lst][i].fi >= it) continue;
				//if(!ck) continue;
				while(nxt[lst][i].fi < it){
					ans += (1 << i);
				//	assert(arr[nxt[lst][i].se] == nxt[lst][i].fi);
					lst = nxt[lst][i].se;
				}
				//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;
				//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 << "OK " << it << " " << it + l + 1 << " " << (*it2).se << "\n";
				lst = mn.se;
			}
		//	cout << 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);
	}
	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:137:7: warning: variable 'ck' set but not used [-Wunused-but-set-variable]
  137 |  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 352 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
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 352 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 3023 ms 6212 KB Output is correct
8 Correct 4899 ms 7472 KB Output is correct
9 Execution timed out 9005 ms 17416 KB Time limit exceeded
10 Halted 0 ms 0 KB -

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 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 3023 ms 6212 KB Output is correct
8 Correct 4899 ms 7472 KB Output is correct
9 Execution timed out 9005 ms 17416 KB Time limit exceeded
10 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 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 3023 ms 6212 KB Output is correct
8 Correct 4899 ms 7472 KB Output is correct
9 Execution timed out 9005 ms 17416 KB Time limit exceeded
10 Halted 0 ms 0 KB -