oj.uz

Submission #752434

# Submission time Handle Problem Language Result Execution time Memory
752434 2023-06-03T03:13:21 Z minhcool Dancing Elephants (IOI11_elephants) C++17
50 / 100
 8537 ms 13376 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];
 
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();
	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;
				int temp = nxt[lst][i];
				while(ok[temp] && arr[temp] < it){
					ans += (1 << i);
				//	assert(arr[nxt[lst][i].se] == nxt[lst][i].fi);
					lst = temp;
					temp = nxt[lst][i];
				}
				//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:141:7: warning: variable 'ck' set but not used [-Wunused-but-set-variable]
  141 |  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 1133 ms 5196 KB Output is correct
8 Correct 1557 ms 6056 KB Output is correct
9 Correct 4204 ms 13356 KB Output is correct
10 Correct 5172 ms 13352 KB Output is correct
11 Correct 8537 ms 13352 KB Output is correct
12 Correct 6853 ms 13364 KB Output is correct
13 Correct 3989 ms 13376 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 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 1133 ms 5196 KB Output is correct
8 Correct 1557 ms 6056 KB Output is correct
9 Correct 4204 ms 13356 KB Output is correct
10 Correct 5172 ms 13352 KB Output is correct
11 Correct 8537 ms 13352 KB Output is correct
12 Correct 6853 ms 13364 KB Output is correct
13 Correct 3989 ms 13376 KB Output is correct
14 Correct 2289 ms 6288 KB Output is correct
15 Incorrect 29 ms 5964 KB Output isn't correct
16 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 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1133 ms 5196 KB Output is correct
8 Correct 1557 ms 6056 KB Output is correct
9 Correct 4204 ms 13356 KB Output is correct
10 Correct 5172 ms 13352 KB Output is correct
11 Correct 8537 ms 13352 KB Output is correct
12 Correct 6853 ms 13364 KB Output is correct
13 Correct 3989 ms 13376 KB Output is correct
14 Correct 2289 ms 6288 KB Output is correct
15 Incorrect 29 ms 5964 KB Output isn't correct
16 Halted 0 ms 0 KB -