Submission #1012121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012121		amirhoseinfar1385	Jousting tournament (IOI12_tournament)	C++17	100 / 100	169 ms	21176 KiB

tournament

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,lg=18;
int all[maxn],n,c,r,kaf=(1<<lg);
struct segment{
	struct node{
		int mina,maxa;
		int lazy,lazygozash;
		node(){
			lazy=0;
			lazygozash=-1;
		}
	};
	node seg[(1<<(lg+1))];
	segment(){
		for(int i=(1<<(lg+1))-1;i>=0;i--){
			if(i>=kaf){
				seg[i].maxa=seg[i].mina=i-kaf;
			}else{
				seg[i].maxa=max(seg[(i<<1)].maxa,seg[(i<<1)^1].maxa);
				seg[i].mina=min(seg[(i<<1)].mina,seg[(i<<1)^1].mina);
			}
		}
	}
	void calc(int i){
		if(i>=kaf){
			if(seg[i].lazygozash!=-1){
				seg[i].mina=seg[i].maxa=seg[i].lazygozash;
				seg[i].lazygozash=-1;
			}
			seg[i].mina+=seg[i].lazy;
			seg[i].maxa+=seg[i].lazy;
			seg[i].lazy=0;
			return ;
		}
		int mnav,mndov,mxav,mxdov;
		if(seg[(i<<1)].lazygozash==-1){
			mnav=seg[(i<<1)].mina;
			mxav=seg[(i<<1)].maxa;
		}else{
			mnav=seg[(i<<1)].lazygozash;
			mxav=seg[(i<<1)].lazygozash;
		}
		mnav+=seg[(i<<1)].lazy;
		mxav+=seg[(i<<1)].lazy;

		if(seg[(i<<1)^1].lazygozash==-1){
			mndov=seg[(i<<1)^1].mina;
			mxdov=seg[(i<<1)^1].maxa;
		}else{
			mndov=seg[(i<<1)^1].lazygozash;
			mxdov=seg[(i<<1)^1].lazygozash;
		}
		mndov+=seg[(i<<1)^1].lazy;
		mxdov+=seg[(i<<1)^1].lazy;

		seg[i].mina=min(mnav,mndov);
		seg[i].maxa=max(mxav,mxdov);
	}
	void shift(int i){
		if(i>=kaf){
			return ;
		}
		if(seg[i].lazygozash!=-1){
			seg[(i<<1)].lazygozash=seg[i].lazygozash;
			seg[(i<<1)^1].lazygozash=seg[i].lazygozash;
			seg[i].lazygozash=-1;
			seg[(i<<1)].lazy=seg[(i<<1)^1].lazy=0;
		}
		seg[(i<<1)].lazy+=seg[i].lazy;
		seg[(i<<1)^1].lazy+=seg[i].lazy;
		seg[i].lazy=0;
	}
	void ins(int i,int l,int r,int tl,int tr,int w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			shift(i);
			calc(i);
			seg[i].lazygozash=w;
			shift(i);
			calc(i);
			return ;
		}
		int m=(l+r)>>1;
		shift(i);
		ins((i<<1),l,m,tl,tr,w);
		ins((i<<1)^1,m+1,r,tl,tr,w);
		calc(i);
		return ;
	}
	void upd(int i,int l,int r,int tl,int tr,int w){
		if(l>r||l>tr||r<tl|tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			shift(i);
			calc(i);
			seg[i].lazy+=w;
			shift(i);
			calc(i);
			return ;
		}
		int m=(l+r)>>1;
		shift(i);
		upd((i<<1),l,m,tl,tr,w);
		upd((i<<1)^1,m+1,r,tl,tr,w);
		calc(i);
		return ;
	}
	int pors(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return 0;
		}
		shift(i);
		calc(i);
		if(l>=tl&&r<=tr){
			return seg[i].mina;
		}
		int m=(l+r)>>1;
		return pors((i<<1),l,m,tl,tr)+pors((i<<1)^1,m+1,r,tl,tr);
	}
	int findakh(int i,int l,int r,int tl,int tr,int w){
		shift(i);
		calc(i);
		if(l>r||l>tr||r<tl||tl>tr||seg[i].mina>w){
			return -1;
		}
		if(l==r){
			return l;
		}
		int m=(l+r)>>1;
		int ret=findakh((i<<1)^1,m+1,r,tl,tr,w);
		if(ret==-1){
			ret=findakh((i<<1),l,m,tl,tr,w);
		}
		return ret;
	}
	int findav(int i,int l,int r,int tl,int tr,int w){
		shift(i);
		calc(i);
		if(l>r||l>tr||r<tl||tl>tr||seg[i].maxa<w){
			return -1;
		}
		if(l==r){
			return l;
		}
		int m=(l+r)>>1;
		int ret=findav((i<<1),l,m,tl,tr,w);
		if(ret==-1){
			ret=findav((i<<1)^1,m+1,r,tl,tr,w);
		}
		return ret;
	}
}seg1,seg2;
vector<pair<int,int>>alle;
int last[maxn];

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
	n=N;
	c=C;
	r=R;
	int ls=-1;
	for(int i=0;i<n-1;i++){
		all[i]=K[i];
		if(all[i]>r){
			ls=i;
		}
		last[i]=ls;
	}
	alle.resize(c);
	for(int i=0;i<c;i++){
		alle[i]=make_pair(S[i],E[i]);
		alle[i].first=seg1.findav(1,0,kaf-1,0,n-1,alle[i].first);
		alle[i].second=seg1.findakh(1,0,kaf-1,0,n-1,alle[i].second);
		if(last[alle[i].second-1]<alle[i].first){
			seg2.upd(1,0,kaf-1,alle[i].first,alle[i].second,1);
		}
		seg1.ins(1,0,kaf-1,alle[i].first,alle[i].second,S[i]);
		seg1.upd(1,0,kaf-1,alle[i].second+1,n,-E[i]+S[i]);
	//	cout<<i<<" "<<alle[i].first<<" "<<alle[i].second<<endl;
	//	for(int i=0;i<n;i++){
	//		cout<<seg1.pors(1,0,kaf-1,i,i)<<" ";
	//	}
	//	cout<<"\n";
	}
	pair<int,int>res;
	res=make_pair(-1,1);
	for(int i=0;i<n;i++){
		res=max(res,make_pair(seg2.pors(1,0,kaf-1,i,i)-i,-i));
	}
	return -res.second;
}

Compilation message (stderr)

tournament.cpp: In member function 'void segment::upd(int, int, int, int, int, int)':
tournament.cpp:94:18: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   94 |   if(l>r||l>tr||r<tl|tl>tr){
      |                 ~^~~

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