Submission #797356

#	Time	Username	Problem	Language	Result	Execution time	Memory
797356		firewater	The Big Prize (IOI17_prize)	C++14	0 / 100	88 ms	2356 KiB

prize

#include "prize.h"
#include <vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;






#define MX 202300
int n,m,l,r,mx,mid,x;
vector<int>c;
struct Tree
{
	#define ls x*2
	#define rs x*2+1
	int s[MX<<2];
	void push_up(int x)
	{
		s[x]=s[ls]+s[rs];
		return;
	}
	void build(int x,int l,int r)
	{
		s[x]=0;
		if(l==r)return;
		int mid=l+r>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
		return;
	}
	void add(int x,int l,int r,int y)
	{
		if(l==r){
			s[x]++;
			return;
		}
		int mid=l+r>>1;
		if(y<=mid)add(ls,l,mid,y);
		else add(rs,mid+1,r,y);
		push_up(x);
		return;
	}
	int ask(int x,int L,int R,int l,int r)
	{
		if(L==l&&R==r)return s[x];
		int mid=L+R>>1;
		if(r<=mid)return ask(ls,L,mid,l,r);
		else if(l>mid)return ask(rs,mid+1,R,l,r);
		else return ask(ls,L,mid,l,mid)+ask(rs,mid+1,R,mid+1,r);
	}
	int askk(int x,int l,int r,int k)
	{
		if(l==r)return l;
		int mid=l+r>>1;
		if(mid-l+1-s[ls]>=k)return askk(ls,l,mid,k);
		else return askk(rs,mid+1,r,k-(mid-l+1-s[ls]));
	}
}T;
int find_best(int N) {
	n=N;
	mx=0;
	for(int i=1;i<=min(500,n);++i){
		c=ask(i-1);
		mx=max(mx,c[0]+c[1]);
	}
	m=n;
	T.build(1,1,n);
	while(1<=m){
		l=1;r=m;
		while(l<r){
			mid=l+r+1>>1;
			x=T.askk(1,1,n,mid);
			c=ask(x-1);
			if(c[0]+c[1]!=mx){
				l=mid;
				break;
			}
			if(c[0]>T.ask(1,1,n,1,x-1))r=mid-1;
			else l=mid;
		}
		x=T.askk(1,1,n,l);
		if(c[0]+c[1]==0)return x-1;
		T.add(1,1,n,x);
		m--;
	}
}

Compilation message (stderr)

prize.cpp: In member function 'void Tree::build(int, int, int)':
prize.cpp:32:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |   int mid=l+r>>1;
      |           ~^~
prize.cpp: In member function 'void Tree::add(int, int, int, int)':
prize.cpp:43:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |   int mid=l+r>>1;
      |           ~^~
prize.cpp: In member function 'int Tree::ask(int, int, int, int, int)':
prize.cpp:52:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |   int mid=L+R>>1;
      |           ~^~
prize.cpp: In member function 'int Tree::askk(int, int, int, int)':
prize.cpp:60:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |   int mid=l+r>>1;
      |           ~^~
prize.cpp: In function 'int find_best(int)':
prize.cpp:77:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |    mid=l+r+1>>1;
      |        ~~~^~
prize.cpp:92:1: warning: control reaches end of non-void function [-Wreturn-type]
   92 | }
      | ^

• Subtask 1: 0 / 20
• Subtask 2: 0 / 80