Submission #1047450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047450		vjudge1	Index (COCI21_index)	C++17	20 / 110	30 ms	50136 KiB

index

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second

using namespace std;
using ll = long long;
const ll MAX_P = (2e5);

template<typename T> ostream& operator<<(ostream& os, vector<T> vec){for(auto it:vec){os << it << " ";} return os;}

ll n,q;
vector<ll> arr;
vector<ll> roots;

ll last_node;
ll val[(ll)(1e6)];
ll n_left[(ll)(1e6)];
ll n_right[(ll)(1e6)];
unordered_map<ll,ll> num2comp;
unordered_map<ll,ll> comp2num;

ll build(ll l, ll r){
	if(l == r){
		ll nd = ++last_node;
		val[nd] = 0;
		return nd;
	}

	ll nd = ++last_node;
	ll m = (r-l)/2+l;
	n_left[nd] = build(l,m);
	n_right[nd] = build(m+1,r);

	return nd;
}

ll get_val(ll nd, ll tl, ll tr, ll l, ll r){
	if(max<ll>(l,tl) > min<ll>(r,tr)){return 0;}
	if(tl <= l && r <= tr){return val[nd];}

	ll m = (r-l)/2+l;
	return get_val(n_left[nd], tl, tr, l, m)+get_val(n_right[nd], tl, tr, m+1, r);
}

ll upd(ll nd, ll tar, ll del, ll l, ll r){
	if(l == r){
		ll new_nd = ++last_node;
		val[new_nd] = val[nd]+del;
		return new_nd;
	}

	ll new_nd = ++last_node;

	ll m = (r-l)/2+l;

	n_left[new_nd] = n_left[nd];
	n_right[new_nd] = n_right[nd];

	if(tar <= m){
		n_left[new_nd] = upd(n_left[new_nd], tar, del, l, m);
	}else{
		n_right[new_nd] = upd(n_right[new_nd], tar, del, m+1, r);
	}

	val[new_nd] = val[n_left[new_nd]]+val[n_right[new_nd]];

	return new_nd;
}

ll bin_search(ll n1, ll n2){
	ll lo = 0; ll hi = MAX_P;

	while(lo < hi){
		ll m = (hi-lo+1)/2+lo;

		ll val = get_val(n2, m, MAX_P, 0, MAX_P)-get_val(n1, m, MAX_P, 0, MAX_P);

		if(val >= m){
			lo = m;
		}else{
			hi = m-1;
		}
	}

	return lo;
}

void dfs(ll nd, string str){
	cout << str << " " << val[nd] << endl;

	if(n_left[nd] != 0){
		dfs(n_left[nd], str+"L");
	}
	if(n_right[nd] != 0){
		dfs(n_right[nd], str+"R");
	}
}

void solve(){

	cin >> n >> q;
	last_node = -1;
	arr.resize(n);

	for(ll i=0; i<n; i++){
		cin >> arr[i];
	}

	/*
	vector<ll> psd_arr = arr.copy();

	sort(psd_arr.begin(), psd_arr.end());

	ll last_ind = 0;
	for(ll i=0; i<n; i++){
		if(num2comp[psd_arr[i]] == 0){
			num2comp[psd_arr[i]] = ++last_ind;
			comp2num[last_ind] = psd_arr[i];
		}
	}

	for(ll i=0; i<n; i++){
		arr[i] = comp2num[arr[i]];
	}
	*/

	roots.pb(build(0,MAX_P));

	for(ll i=0; i<n; i++){
		roots.pb(upd(roots[roots.size()-1], arr[i], 1, 0, MAX_P));
	}


	/*
	while(true){
		ll k,l,r;
		cin >> k >> l >> r;

		cout << get_val(roots[k], l, r, 0, MAX_P) << endl;
	}
	*/

	
	for(ll quer=0; quer<q; quer++){
		ll l,r;
		cin >> l >> r;

		//dontforget n1 = l-1;
		ll val = bin_search(roots[l-1], roots[r]);

		cout << val << endl;
	}

}

int main(){




	solve();
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 40
• Subtask 3: 0 / 50