oj.uz

Submission #59265

# Submission time Handle Problem Language Result Execution time Memory
59265 2018-07-21T11:13:28 Z TadijaSebez Holiday (IOI14_holiday) C++11
100 / 100
 2365 ms 21112 KB 
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
#define ll long long
const int N=100050;
const int M=2*N;
const int H=4*N;
ll max(ll a, ll b){ return a>b?a:b;}
int ls[M],rs[M],sz[M],tsz,root;
ll sum[M];
void init(){ for(int i=1;i<=tsz;i++) ls[i]=rs[i]=sz[i]=sum[i]=0;tsz=root=0;}
void Set(int &c, int ss, int se, int qi, int f, ll val)
{
	if(!c) c=++tsz;
	sz[c]+=f;sum[c]+=val;
	if(ss==se) return;
	int mid=ss+se>>1;
	if(qi<=mid) Set(ls[c],ss,mid,qi,f,val);
	else Set(rs[c],mid+1,se,qi,f,val);
}
ll Get(int c, int ss, int se, int k)
{
	if(ss==se){ if(k>=sz[c]) return sum[c];return 0;}
	int mid=ss+se>>1;
	if(sz[ls[c]]>k) return Get(ls[c],ss,mid,k);
	else return sum[ls[c]]+Get(rs[c],mid+1,se,k-sz[ls[c]]);
}
int a[N],b[N],id[N],posL[H],posR[H],st,L=1,R;
ll solL[H],solR[H];
void Add(int i){ Set(root,1,N,id[i],1,a[i]);}
void Del(int i){ Set(root,1,N,id[i],-1,-a[i]);}
void Build(int l, int r)
{
	int i;
	if(l>R || L>r || L>R || l>r)
	{
		for(i=L;i<=R;i++) Del(i);
		for(i=l;i<=r;i++) Add(i);
	}
	else
	{
		for(i=l;i<L;i++) Add(i);
		for(i=L;i<l;i++) Del(i);
		for(i=r+1;i<=R;i++) Del(i);
		for(i=R+1;i<=r;i++) Add(i);
	}
	L=l;R=r;
}
void SolveR(int l, int r, int s, int e, int mul)
{
	if(l>r) return;
	int mid=l+r>>1;
	Build(st+(mul==1),s-1);
	int i;
	for(i=s;i<=e;i++)
	{
		Add(i);
		if(mid-mul*(i-st)<0) continue;
		ll tmp=Get(root,1,N,mid-mul*(i-st));
		if(solR[mid]<tmp || !posR[mid]) posR[mid]=i,solR[mid]=tmp;
	}
	R=e;
	if(!posR[mid]) posR[mid]=s;
	SolveR(l,mid-1,s,posR[mid],mul);
	SolveR(mid+1,r,posR[mid],e,mul);
}
void SolveL(int l, int r, int s, int e, int mul)
{
	if(l>r) return;
	int mid=l+r>>1;
	Build(e+1,st-(mul==1));
	//printf("L:%i R:%i l:%i r:%i s:%i e:%i\n",L,R,l,r,s,e);
	int i;
	for(i=e;i>=s;i--)
	{
		Add(i);
		if(mid-mul*(st-i)<0) continue;
		ll tmp=Get(root,1,N,mid-mul*(st-i));
		//printf("%i %i\n",i,tmp);
		if(solL[mid]<tmp || !posL[mid]) posL[mid]=i,solL[mid]=tmp;
	}
	L=s;
	if(!posL[mid]) posL[mid]=e;
	SolveL(l,mid-1,posL[mid],e,mul);
	SolveL(mid+1,r,s,posL[mid],mul);
}
void init2(){ for(int i=0;i<H;i++) posL[i]=posR[i]=solL[i]=solR[i]=0;}
bool comp(int i, int j){ return a[i]>a[j];}
ll findMaxAttraction(int n, int start, int d, int at[])
{
	int i;
	//scanf("%i %i %i",&n,&st,&d);
	st=start;
	st++;
	//for(i=1;i<=n;i++) scanf("%i",&a[i]),b[i]=i;
	for(i=1;i<=n;i++) a[i]=at[i-1],b[i]=i;
	sort(b+1,b+1+n,comp);
	for(i=1;i<=n;i++) id[b[i]]=i;
	if(d==0) return 0;
	ll sol=0;
	SolveR(1,d,st,n,2);
	SolveL(1,d,1,st-1,1);
	//printf("1\n");
	//for(i=1;i<=d;i++) printf("L:%i R:%i\n",solL[i],solR[i]);
	for(i=0;i<=d;i++) sol=max(sol,solR[i]+solL[d-i]);
	init2();
	SolveR(1,d,st+1,n,1);
	SolveL(1,d,1,st,2);
	//printf("2\n");
	//for(i=1;i<=d;i++) printf("L:%i R:%i\n",solL[i],solR[i]);
	for(i=0;i<=d;i++) sol=max(sol,solL[i]+solR[d-i]);
	init();
	for(i=st;i<=n;i++)
	{
		Add(i);
		if(d-i+st>0) sol=max(sol,Get(root,1,N,d-i+st));
	}
	init();
	for(i=st;i>=1;i--)
	{
		Add(i);
		if(d-st+i>0) sol=max(sol,Get(root,1,N,d-st+i));
	}
	//printf("%lld\n",sol);
	return sol;
}

Compilation message

holiday.cpp: In function 'void Set(int&, int, int, int, int, long long int)':
holiday.cpp:18:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
holiday.cpp: In function 'long long int Get(int, int, int, int)':
holiday.cpp:25:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
holiday.cpp: In function 'void SolveR(int, int, int, int, int)':
holiday.cpp:53:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=l+r>>1;
          ~^~
holiday.cpp: In function 'void SolveL(int, int, int, int, int)':
holiday.cpp:71:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=l+r>>1;
          ~^~
grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9720 KB Output is correct
2 Correct 13 ms 9836 KB Output is correct
3 Correct 12 ms 9892 KB Output is correct
4 Correct 12 ms 9892 KB Output is correct
5 Correct 12 ms 9892 KB Output is correct
6 Correct 14 ms 9892 KB Output is correct
7 Correct 14 ms 9892 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1214 ms 15576 KB Output is correct
2 Correct 1146 ms 16008 KB Output is correct
3 Correct 1117 ms 16204 KB Output is correct
4 Correct 1173 ms 16500 KB Output is correct
5 Correct 1962 ms 16500 KB Output is correct
6 Correct 635 ms 16500 KB Output is correct
7 Correct 896 ms 16500 KB Output is correct
8 Correct 1412 ms 16500 KB Output is correct
9 Correct 525 ms 16500 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 16500 KB Output is correct
2 Correct 38 ms 16500 KB Output is correct
3 Correct 37 ms 16500 KB Output is correct
4 Correct 38 ms 16500 KB Output is correct
5 Correct 32 ms 16500 KB Output is correct
6 Correct 18 ms 16500 KB Output is correct
7 Correct 17 ms 16500 KB Output is correct
8 Correct 17 ms 16500 KB Output is correct
9 Correct 17 ms 16500 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1333 ms 18196 KB Output is correct
2 Correct 1338 ms 19104 KB Output is correct
3 Correct 614 ms 19104 KB Output is correct
4 Correct 37 ms 19104 KB Output is correct
5 Correct 19 ms 19104 KB Output is correct
6 Correct 19 ms 19104 KB Output is correct
7 Correct 15 ms 19104 KB Output is correct
8 Correct 2249 ms 20312 KB Output is correct
9 Correct 2365 ms 21112 KB Output is correct