oj.uz

Submission #903235

# Submission time Handle Problem Language Result Execution time Memory
903235 2024-01-11T06:27:50 Z Faisal_Saqib Holiday (IOI14_holiday) C++17
30 / 100
 1167 ms 2944 KB 
#pragma once
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define ll long long
const int N=30000;
int MN=3003;
int seg_cnt[N];
long long seg_sum[N];
void Update(int i,ll val=-1,int v=1,int s=0,int e=MN)
{
	if(i<s or e<i)
		return;
	if(s==e)
	{
		seg_cnt[v]++;
		if(val==-1)
			seg_sum[v]+=i;
		else
		{
			seg_sum[v]+=val;
		}
		return;
	}
	int mid=(s+e)/2;
	Update(i,val,2*v,s,mid);
	Update(i,val,2*v+1,1+mid,e);
	seg_cnt[v]=seg_cnt[2*v]+seg_cnt[2*v+1];
	seg_sum[v]=seg_sum[2*v]+seg_sum[2*v+1];
}
void Update1(int i,ll val=-1,int v=1,int s=0,int e=MN)
{
	if(i<s or e<i)
		return;
	if(s==e)
	{
		seg_cnt[v]--;
		if(val==-1)
			seg_sum[v]-=i;
		else
			seg_sum[v]-=val;
		return;
	}
	int mid=(s+e)/2;
	Update1(i,val,2*v,s,mid);
	Update1(i,val,2*v+1,1+mid,e);
	seg_cnt[v]=seg_cnt[2*v]+seg_cnt[2*v+1];
	seg_sum[v]=seg_sum[2*v]+seg_sum[2*v+1];
}
int get_cnt(int l,int r,int v=1,int s=0,int e=MN)
{
	if(r<s or e<l)
		return 0;
	if(l<=s and e<=r)
		return seg_cnt[v];
	int mid=(s+e)/2;
	return get_cnt(l,r,2*v,s,mid)+get_cnt(l,r,2*v+1,mid+1,e);
}
long long get_sum(int l,int r,int v=1,int s=0,int e=MN)
{
	if(r<s or e<l)
		return 0;
	if(l<=s and e<=r)
		return seg_sum[v];
	int mid=(s+e)/2;
	return get_sum(l,r,2*v,s,mid)+get_sum(l,r,2*v+1,mid+1,e);
}
long long findMaxAttraction(int n, int cc, int d, int a[])
{
	int mx=0;
	for(int i=0;i<n;i++)
		mx=max(mx,a[i]);
	if(mx<=100 and cc==0)
	{
		long long ans=0;
		for(int i=0;i<n;i++)
		{
			Update(a[i]);
			// // Find the maximum point such that (get_cnt(s,100)+i)>d
			int s=-1;
			int e=MN+1;
			while(s+1<e)
			{
				int mid=(s+e)/2;
				if((get_cnt(mid,MN)+i)>d)
				{
					s=mid;
				}
				else
				{
					e=mid;
				}
			}
			// cout<<"ad\n";
			// cout<<"HASD "<<get_cnt(s,100)<<' '<<i<<' '<<d<<endl;
			long long cur=get_sum(s+1,MN);
			// cout<<"Hola "<<i<<' '<<s<<' '<<cur<<endl;;
			if(s!=-1)
			{
				cur+=(s*(d-i-get_cnt(s+1,MN)));
			}
			ans=max(ans,cur);
			// Now for s We can see how many can we pick
		}
		return ans;
	}
	else
	{
		// cout<<"asd\n";
		vector<int> op,dp;
		for(int i=0;i<n;i++)
		{
			op.push_back(a[i]);
		}
		sort(begin(op),end(op));
		for(int i=0;i<n;i++)
			dp.push_back(lower_bound(begin(op),end(op),a[i])-begin(op));
		long long ans=0;
		for(int left=cc;left>=0;left--)
		{
			Update(dp[left],a[left]);
			{
				int right=cc;
				ll tmie=min(right-cc,cc-left)+right-left;
				if(tmie<=d)
				{
					int s=-1;
					int e=MN+1;
					while(s+1<e)
					{
						int mid=(s+e)/2;
						if((get_cnt(mid,MN)+tmie)>d)
						{
							s=mid;
						}
						else
						{
							e=mid;
						}
					}
					long long cur=get_sum(s+1,MN);
					if(s!=-1)
					{
						cur+=(a[s]*(d-tmie-get_cnt(s+1,MN)));
					}
					ans=max(ans,cur);
				}
			}
			for(int right=cc+1;right<n;right++)
			{
				Update(dp[right],a[right]);
				ll tmie=min(right-cc,cc-left)+right-left;
				if(tmie>d)
					continue;
				int s=-1;
				int e=MN+1;
				while(s+1<e)
				{
					int mid=(s+e)/2;
					if((get_cnt(mid,MN)+tmie)>d)
					{
						s=mid;
					}
					else
					{
						e=mid;
					}
				}
				long long cur=get_sum(s+1,MN);
				if(s!=-1)
				{
					cur+=(a[s]*(d-tmie-get_cnt(s+1,MN)));
				}
				ans=max(ans,cur);
			}
			for(int right=cc+1;right<n;right++)
				Update1(dp[right],a[right]);
		}
		return ans;
	}
	return 0;
}

Compilation message

holiday.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 872 KB Output is correct
3 Correct 1 ms 872 KB Output is correct
4 Correct 0 ms 868 KB Output is correct
5 Correct 0 ms 1112 KB Output is correct
6 Correct 0 ms 860 KB Output is correct
7 Correct 0 ms 860 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 604 KB Output is correct
2 Correct 54 ms 856 KB Output is correct
3 Correct 81 ms 836 KB Output is correct
4 Correct 61 ms 860 KB Output is correct
5 Correct 54 ms 860 KB Output is correct
6 Correct 16 ms 856 KB Output is correct
7 Correct 30 ms 856 KB Output is correct
8 Correct 41 ms 864 KB Output is correct
9 Correct 12 ms 860 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 860 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 3 ms 856 KB Output is correct
4 Correct 1167 ms 948 KB Output is correct
5 Correct 832 ms 952 KB Output is correct
6 Correct 20 ms 856 KB Output is correct
7 Correct 83 ms 880 KB Output is correct
8 Incorrect 96 ms 860 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 2000 KB Output is correct
2 Incorrect 57 ms 2944 KB Output isn't correct
3 Halted 0 ms 0 KB -