Submission #121907

#	Time	Username	Problem	Language	Result	Execution time	Memory
121907		baluteshih	Jousting tournament (IOI12_tournament)	C++14	100 / 100	103 ms	12160 KiB

tournament

#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int seg[400005],lazy[400005],cnt[100005];
vector<pii> oper[100005];
pii rel[100005];

void build(int l,int r,int rt)
{
	if(l==r)
		return seg[rt]=1,void();
	int m=l+r>>1;
	build(l,m,rt<<1),build(m+1,r,rt<<1|1);
	seg[rt]=seg[rt<<1]+seg[rt<<1|1];
}

void down(int rt)
{
	if(!lazy[rt]) return;
	seg[rt<<1]=seg[rt<<1|1]=0,lazy[rt<<1]=lazy[rt<<1|1]=1;
	lazy[rt]=0;
}

void modify(int L,int R,int l,int r,int rt)
{
	if(l!=r) down(rt);
	if(L<=l&&R>=r)
		return seg[rt]=0,lazy[rt]=1,void();
	int m=l+r>>1;
	if(L<=m) modify(L,R,l,m,rt<<1);
	if(R>m) modify(L,R,m+1,r,rt<<1|1);
	seg[rt]=seg[rt<<1]+seg[rt<<1|1];
}

int query(int x,int l,int r,int rt)
{
	if(l!=r) down(rt);
	if(l==r) return l;
	int m=l+r>>1;
	if(seg[rt<<1]>=x) return query(x,l,m,rt<<1);
	return query(x-seg[rt<<1],m+1,r,rt<<1|1);
}

void build2(int l,int r,int rt,int *K)
{
	if(l==r)
		return seg[rt]=K[l-1],void();
	int m=l+r>>1;
	build2(l,m,rt<<1,K),build2(m+1,r,rt<<1|1,K);
	seg[rt]=max(seg[rt<<1],seg[rt<<1|1]);
}

int query2(int L,int R,int l,int r,int rt)
{
	if(L<=l&&R>=r)
		return seg[rt];
	int m=l+r>>1;
	if(R<=m) return query2(L,R,l,m,rt<<1);
	if(L>m) return query2(L,R,m+1,r,rt<<1|1);
	return max(query2(L,R,l,m,rt<<1),query2(L,R,m+1,r,rt<<1|1));
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
	int ans=-1,ansn=0;
	build(0,N,1);
	for(int i=0;i<C;++i)
	{
		int l=query(S[i]+1,0,N,1),r=query(E[i]+2,0,N,1);
		rel[i]=MP(l,r-1),modify(l+1,r-1,0,N,1);
	}
	build2(1,N,1,K);
	for(int i=0;i<C;++i)
	{
		int mx=query2(rel[i].F+1,rel[i].S,1,N,1);
		if(rel[i].F)
			oper[rel[i].F].pb(MP(max(mx,K[rel[i].F-1]),max(mx,R))),++cnt[max(mx,K[rel[i].F-1])];
		else
			oper[rel[i].F].pb(MP(N,max(mx,R))),++cnt[N];
		if(rel[i].S+1<N)
			oper[rel[i].S+1].pb(MP(max(mx,R),max(mx,K[rel[i].S])));
	}
	for(int i=0;i<N;++i)
	{
		for(auto j:oper[i])
			--cnt[j.F],++cnt[j.S];
		if(cnt[R]>ans)
			ans=cnt[R],ansn=i;
	}
	return ansn;
}

Compilation message (stderr)

tournament.cpp: In function 'void build(int, int, int)':
tournament.cpp:24:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
tournament.cpp: In function 'void modify(int, int, int, int, int)':
tournament.cpp:41:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
tournament.cpp: In function 'int query(int, int, int, int)':
tournament.cpp:51:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
tournament.cpp: In function 'void build2(int, int, int, int*)':
tournament.cpp:60:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
tournament.cpp: In function 'int query2(int, int, int, int, int)':
tournament.cpp:69:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~

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