Submission #44592

#	Time	Username	Problem	Language	Result	Execution time	Memory
44592		mohammad_kilani	Jousting tournament (IOI12_tournament)	C++17	0 / 100	221 ms	15236 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] , seg3[4 * 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){
	seg3[idx] = 1e9;
	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;
}

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

int getmin(int idx,int n){
	int s = 0 ,e = n -1 , mid = (s + e) / 2 , res = 1e9 , node = 1;
	while(true){
		res = min(res,seg3[node]);
		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;
}

int GetBestPosition(int n, int C, int R, int *K, int *S, int *E) {
	build(0,n-1,1);
	memset(lazy,-1,sizeof(lazy));
	nxt[n-1] = n - 1;
	for(int i=n-2;i>=0;i--){
		if(K[i] > R)
			nxt[i] = i;
		else
			nxt[i] = nxt[i+1];
	}
	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);
		if(nxt[S[i]] <= E[i] - 1){
			update3(0,n-1,1,S[i],E[i],i);
		}
	}
	sort(v.begin(),v.end());
	int maxval = -1 , bestidx = -1;
	for(int i=0;i<n-1;i++){
		tmp = getless(i,getmin(i,n),n);
		if(tmp > maxval){
			maxval = tmp;
			bestidx = i;
		}
	}
  	return bestidx;
}

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