Submission #696607

#	Time	Username	Problem	Language	Result	Execution time	Memory
696607		vjudge1	Holiday (IOI14_holiday)	C++14	100 / 100	415 ms	38080 KiB

holiday

#include<bits/stdc++.h>
#define ll long long
#define lll __int128
#define db double
#define ld long double
#define pii pair<int,int>
#define fi first
#define se second
#define vi vector<int>
using namespace std;
namespace IO
{
	const int SZ=1<<20;
	char gchar()
	{
	    static char buf[SZ];
	    static int i=SZ;
	    if(i==SZ)i=0,fread(buf,1,SZ,stdin);
	    return buf[i++];
	}
	void pchar(char c)
	{
	    static char buf[SZ];
	    static int i=0;
	    if(c)buf[i++]=c;
	    if(!c||i==SZ)fwrite(buf,1,i,stdout),i=0;
	}
	void pstr(string s,char end='\n')
	{
		for(char c:s)pchar(c);
		pchar(end);
	}
	template<typename T>void read(T &x)
	{
	    x=0;int f=1;
	    static char c;
	    while((c=gchar())>'9'||c<'0')if(c=='-')f=-1;
	    x=c-'0';
	    while((c=gchar())>='0'&&c<='9')
			x=(x<<1)+(x<<3)+(c^48);
		x*=f;
	}
	template<typename T,typename ...Args>void read(T &x,Args&...args){read(x),read(args...);}
	template<typename T>void i_write(T x)
	{
	    if(x>9)i_write(x/10);
	    pchar(x%10+'0');
	}
	template<typename T>void write(T x,char end='\n')
	{
	    if(x<0)pchar('-'),x=-x;
	    if(x>9)i_write(x/10);
	    pchar(x%10+'0');
	    pchar(end);
	}
}
using IO::read;
using IO::write;
const int N=1e5+10;
int n,s,d,rt[N],cnt;
ll a[N],b[N];
struct SegmentTree
{
	int ls[N<<5],rs[N<<5],c[N<<5],idx;
	ll s[N<<5];
	void pushup(int p){s[p]=s[ls[p]]+s[rs[p]],c[p]=c[ls[p]]+c[rs[p]];}
	void upd(int &p,int q,int l,int r,int x)
	{
		p=++idx,ls[p]=ls[q],rs[p]=rs[q],c[p]=c[q],s[p]=s[q];
		if(l==r)return c[p]++,s[p]+=b[x],void();
		int mid=(l+r)>>1;
		if(x<=mid)upd(ls[p],ls[q],l,mid,x);
		else upd(rs[p],rs[q],mid+1,r,x);
		pushup(p);
	}
	ll ask(int p,int q,int l,int r,int k)
	{
		if(k<=0)return 0;
		if(c[p]-c[q]<k)return s[p]-s[q];
		if(l==r)return b[l]*k;
		int mid=(l+r)>>1;
		if(k<=c[rs[p]]-c[rs[q]])return ask(rs[p],rs[q],mid+1,r,k);
		return ask(ls[p],ls[q],l,mid,k-(c[rs[p]]-c[rs[q]]))+s[rs[p]]-s[rs[q]];
	}
}sgt;
ll calc(int l,int r){return sgt.ask(rt[r],rt[l-1],1,cnt,d-(2*(r-s)+s-l));}
ll ans;
void solve(int l,int r,int L,int R)
{
    if(l>r)return;
    if(L==R)
    {
        for(int i=l;i<=r;i++)ans=max(ans,calc(i,L));
        return;
    }
    int pos=L,mid=(l+r)>>1;ll mx=calc(mid,L);
    for(int i=L+1;i<=R;i++)
    {
        ll v=calc(mid,i);
        if(v>mx)mx=v,pos=i;
    }
    ans=max(ans,mx),solve(l,mid-1,L,pos),solve(mid+1,r,pos,R);
}
void work()
{
    for(int i=1;i<=n;i++)rt[i]=0;
    for(int i=1;i<=sgt.idx;i++)sgt.ls[i]=sgt.rs[i]=sgt.c[i]=sgt.s[i]=0;
    sgt.idx=0;
    for(int i=1;i<=n;i++)sgt.upd(rt[i],rt[i-1],1,cnt,a[i]);
    for(int i=1;i<=s;i++)ans=max(ans,calc(i,s));
    solve(1,s-1,s+1,n);
}
ll findMaxAttraction(int _n,int _s,int _d,int _a[])
{
	n=_n,s=_s+1,d=_d;
	for(int i=1;i<=n;i++)a[i]=_a[i-1],b[i]=a[i];
	sort(b+1,b+n+1),cnt=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
    work();
	s=n-s+1,reverse(a+1,a+n+1);
	work();
	return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'char IO::gchar()':
holiday.cpp:18:24: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |      if(i==SZ)i=0,fread(buf,1,SZ,stdin);
      |                   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53