oj.uz

Submission #228502

# Submission time Handle Problem Language Result Execution time Memory
228502 2020-05-01T09:17:37 Z kig9981 Holiday (IOI14_holiday) C++17
100 / 100
 834 ms 55032 KB 
#include "holiday.h"
#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

struct PST
{
	int l, r, c;
	long long s;
	PST() : l(0), r(0), c(0), s(0) {}
};

const int SZ=1<<17;
PST tree[2222222];
int node_cnt, N, s, d, A[100000];
pair<int,int> x[100000];
long long ans;

void add_tree(int b, int n, int v, int p, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	if(s==e) {
		tree[p].s=v;
		tree[p].c=1;
		return;
	}
	if(n<=m) {
		tree[node_cnt]=PST();
		tree[p].l=node_cnt++;
		tree[p].r=tree[b].r;
		add_tree(tree[b].l,n,v,tree[p].l,s,m);
	}
	else {
		tree[node_cnt]=PST();
		tree[p].r=node_cnt++;
		tree[p].l=tree[b].l;
		add_tree(tree[b].r,n,v,tree[p].r,m+1,e);
	}
	tree[p].s=tree[tree[p].l].s+tree[tree[p].r].s;
	tree[p].c=tree[tree[p].l].c+tree[tree[p].r].c;
}

int kth(int l, int r, int k)
{
	int s=0, e=SZ-1;
	while(s<e) {
		int m=(s+e)>>1;
		if(tree[tree[r].l].c-tree[tree[l].l].c>=k) {
			l=tree[l].l;
			r=tree[r].l;
			e=m;
		}
		else {
			k-=tree[tree[r].l].c-tree[tree[l].l].c;
			l=tree[l].r;
			r=tree[r].r;
			s=m+1;
		}
	}
	return s;
}

long long get_sum(int n1, int n2, int p, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	if(p==0 || n2<n1 || n2<s || e<n1) return 0;
	if(n1<=s && e<=n2) return tree[p].s;
	return get_sum(n1,n2,tree[p].l,s,m)+get_sum(n1,n2,tree[p].r,m+1,e);
}

void solve(int s1, int e1, int s2, int e2)
{
	int m1=(s1+e1)>>1, m2=-1, k;
	long long mx=-1, t;
	if(s1>e1) return;
	for(int i=s2;i<=e2;i++) if(d>2*(s-m1)+i-s) {
		k=kth(m1,i+1,min(d-2*(s-m1)-i+s,i-m1+1));
		if((t=get_sum(0,k,i+1)-get_sum(0,k,m1))>mx) {
			mx=t;
			m2=i;
		}
	}
	if(mx==-1) {
		solve(m1+1,e1,s2,e2);
		return;
	}
	ans=max(ans,mx);
	solve(s1,m1-1,s2,m2);
	solve(m1+1,e1,m2,e2);
}

long long findMaxAttraction(int n, int start, int d, int attraction[])
{
	N=n; s=start; ::d=d;
	if(d==0) return 0;
	for(int i=0;i<N;i++) x[i]={A[i]=attraction[i],i};
	sort(x,x+N);
	node_cnt=N+1;
	for(int i=0;i<N;i++) A[x[i].second]=i;
	for(int i=0;i<N;i++) add_tree(i,N-1-A[i],x[A[i]].first,i+1);
	solve(max(0,s-d+1),s,s,min(s+d-1,N-1));
	reverse(A,A+N); s=N-1-s;
	node_cnt=N+1;
	for(int i=0;i<N;i++) {
		tree[i+1]=PST();
		add_tree(i,N-1-A[i],x[A[i]].first,i+1);
	}
	solve(max(0,s-d+1),s,s,min(s+d-1,N-1));
	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 52480 KB Output is correct
2 Correct 31 ms 52472 KB Output is correct
3 Correct 32 ms 52480 KB Output is correct
4 Correct 30 ms 52472 KB Output is correct
5 Correct 30 ms 52480 KB Output is correct
6 Correct 30 ms 52480 KB Output is correct
7 Correct 30 ms 52472 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 54016 KB Output is correct
2 Correct 137 ms 54008 KB Output is correct
3 Correct 141 ms 54016 KB Output is correct
4 Correct 130 ms 54016 KB Output is correct
5 Correct 143 ms 53880 KB Output is correct
6 Correct 62 ms 52984 KB Output is correct
7 Correct 94 ms 53504 KB Output is correct
8 Correct 109 ms 53632 KB Output is correct
9 Correct 52 ms 52856 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 52608 KB Output is correct
2 Correct 33 ms 52608 KB Output is correct
3 Correct 33 ms 52608 KB Output is correct
4 Correct 41 ms 52608 KB Output is correct
5 Correct 40 ms 52472 KB Output is correct
6 Correct 31 ms 52472 KB Output is correct
7 Correct 32 ms 52480 KB Output is correct
8 Correct 33 ms 52480 KB Output is correct
9 Correct 33 ms 52480 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 54008 KB Output is correct
2 Correct 131 ms 54008 KB Output is correct
3 Correct 183 ms 53268 KB Output is correct
4 Correct 40 ms 52604 KB Output is correct
5 Correct 33 ms 52480 KB Output is correct
6 Correct 34 ms 52604 KB Output is correct
7 Correct 34 ms 52600 KB Output is correct
8 Correct 811 ms 55032 KB Output is correct
9 Correct 834 ms 55032 KB Output is correct