Submission #348310

#	Time	Username	Problem	Language	Result	Execution time	Memory
348310		jamielim	The Big Prize (IOI17_prize)	C++14	0 / 100	54 ms	41708 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

pair<int,int> memo[200005];

struct node{
	int s,e,m;
	int v;
	node *l,*r;
	node(int S,int E){
		s=S;e=E;m=(s+e)/2;
		v=1012345678;
		if(s!=e){l=new node(s,m);r=new node(m+1,e);}
	}
	void upd(int x,int val){
		if(s==e){v=min(v,val);return;}
		if(x<=m)l->upd(x,val);
		else r->upd(x,val);
		v=min(l->v,r->v);
	}
	int qry(int x){
		if(s>=x)return v;
		if(m>x)return min(r->v,l->qry(x));
		return r->qry(x);
	}
}*root=new node(0,200005);

pair<int,int> qry(int x){
	if(memo[x].first!=-1)return memo[x];
	vector<int> v=ask(x);
	root->upd(v[0],x);
	return memo[x]=make_pair(v[0],v[1]);
}

int find_best(int n){
	for(int i=0;i<n;i++)memo[i]=make_pair(-1,-1);
	int k=1;
	while(k*(k+1)<n)k++;
	k++;
	int sz=0;
	pair<int,int> p;
	for(int i=0;i<k;i++){
		p=qry(n/k*i);
		sz=max(sz,p.first+p.second);
	}
	for(int i=0;i<n;i++){
		p=qry(i);
		if(p.first+p.second==0)return i;
		if(p.first+p.second!=sz)continue;
		int l=i,r=root->qry(p.first+1)-1,mid;
		while(l<r){
			mid=(l+r+1)/2;
			if(qry(mid)==p){
				l=mid;
			}else{
				r=mid-1;
			}
		}
		i=l;
	}
	return n;
}
/*
8
3 2 3 1 3 3 2 3
*/

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