Submission #44591

#	Time	Username	Problem	Language	Result	Execution time	Memory
44591		mohammad_kilani	Jousting tournament (IOI12_tournament)	C++17	0 / 100	235 ms	15896 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
const int N = 100010 , LOG = 19;
int tmp , lazy[4 * N] , seg[4 * N]  , waget[N] , nxt[N];
vector< pair<int,pair<int,int> > > v;
vector< int > seg2[4 * N];


inline void fix(int s,int e,int idx){
	if(lazy[idx] == -1)
		return;
	seg[idx] = lazy[idx] * (e - s + 1);
	if(s != e)
		lazy[idx*2] = lazy[idx*2+1] = lazy[idx];
	lazy[idx] = -1;
}

int build(int s,int e,int idx){
	if(s == e) return seg[idx] = 1;
	return seg[idx] = build(s,(s+e)/2,idx*2) + build((s+e)/2+1,e,idx*2+1);
}

int getsum(int s,int e,int idx,int l,int r){
	fix(s,e,idx);
	if(s > r || e < l) return 0;
	if(s >= l && e <= r) return seg[idx];
	return getsum(s,(s+e)/2,idx*2,l,r) + getsum((s+e)/2+1,e,idx*2+1,l,r);
}

int update(int s,int e,int idx,int l,int r,int val){
	fix(s,e,idx);
	if(s > r || e < l) return seg[idx];
	if(s >= l && e <= r){
		lazy[idx] = val;
		fix(s,e,idx);
		return seg[idx];
	}
	return seg[idx] = update(s,(s+e)/2,idx*2,l,r,val) + update((s+e)/2+1,e,idx*2+1,l,r,val);
}

int lower_bound_on_seg(int val,int n){
	int low = 0 , high = n - 1, res = n , mid , cur;
	while(high >= low){
		mid = ((low + high) >> 1);
		cur = getsum(0,n-1,1,0,mid) - 1;
		if(cur >= val){
			res = mid;
			high = mid - 1;
		}
		else
			low = mid + 1;
	}
	return res;
}

void update2(int s,int e,int idx,int l,int r,int val){
	if(s > r || e < l) 
		return ;
	if(s >= l && e <= r){
		seg2[idx].push_back(val);
		return;
	}
	update2(s,(s+e)/2,idx*2,l,r,val);
	update2((s+e)/2+1,e,idx*2+1,l,r,val);
}

int getless(int idx,int val,int n){
	int s = 0 ,e = n -1 , mid = (s + e) / 2 , res = 0 , node = 1;
	while(true){
		res += lower_bound(seg2[node].begin(),seg2[node].end(),val) - seg2[node].begin();
		if(s == e)
			break;
		mid = (s + e) / 2;
		if(idx > mid){
			s = mid + 1;
			node = node * 2 + 1;
		}
		else{
			e = mid;
			node = node * 2;
		}
	}
	return res;
}

set < pair<int,int> > st;
set < pair<int,int> > :: iterator it;

int low , high , res , mid , l;

void add(int r,int idx){
	it = st.lower_bound(make_pair(r,0));
	if(it != st.end() && it->second < idx)
		return;
	low = 0 , high = r, res = r + 1;
	while(high >= low){
		mid = (low + high) / 2;
		it = st.lower_bound(make_pair(mid,0));
		if(it != st.end() || it->second <= idx){
			res = mid;
			high = mid - 1;
		}
		else{
			low = mid + 1;
		}
	}
	it = st.lower_bound(make_pair(res,0));
	while(it != st.end() && it->first <= r){
		st.erase(it);
		it = st.lower_bound(make_pair(res,0));
	}
	st.insert(make_pair(r,idx));
}

void changewaget(int n,int *arr,int r){
	nxt[n] = n;
	for(int i=n-1;i>=0;i--){
		if(arr[i] > r)
			nxt[i] = i;
		else
			nxt[i] = nxt[i+1];
	}
	l = 0;
	for(int i=0;i<n;i++){
		if(arr[i] > r) continue;
		while(l < (int)v.size() && v[l].first <= i){
			add(v[l].second.first,v[l].second.second);
			l++;
		}
		it = st.lower_bound(make_pair(nxt[i]+1,0));
		if(it != st.end())
			waget[i] = min(waget[i],it->second);
	}
}

void changewaget2(int n,int *arr,int r){
	st.clear();
	reverse(arr,arr+n);
	nxt[n] = n;
	for(int i=n-1;i>=0;i--){
		if(arr[i] > r)
			nxt[i] = i;
		else
			nxt[i] = nxt[i+1];
	}
	l = 0;
	for(int i=0;i<n;i++){
		if(arr[i] > r) continue;
		while(l < (int)v.size() && v[l].first <= i){
			add(v[l].second.first,v[l].second.second);
			l++;
		}
		it = st.lower_bound(make_pair(nxt[i]+1,0));
		if(it != st.end())
			waget[n - i - 1] = min(waget[n - i - 1],it->second);
	}
}

int GetBestPosition(int n, int C, int R, int *K, int *S, int *E) {
	build(0,n-1,1);
	memset(lazy,-1,sizeof(lazy));
	for(int i=0;i<C;i++){
		S[i] = lower_bound_on_seg(S[i],n);
		E[i] = lower_bound_on_seg(E[i],n);
		update(0,n-1,1,S[i]+1,E[i],0);
		update2(0,n-1,1,S[i],E[i],i);
		v.push_back(make_pair(S[i],make_pair(E[i],i)));
	}
	sort(v.begin(),v.end());
	for(int i=0;i<n;i++)
		waget[i] = 1e9;
	changewaget(n-1,K,R);
	changewaget2(n-1,K,R);
	int maxval = -1 , bestidx = -1;
	for(int i=0;i<n-1;i++){
		if(K[i] > R) continue;
		tmp = getless(i,waget[i],n);
		if(tmp > maxval){
			maxval = tmp;
			bestidx = i;
		}
	}
  	return bestidx;
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 32
• Subtask 3: 0 / 51