Submission #550612

#	Time	Username	Problem	Language	Result	Execution time	Memory
550612		CSQ31	Holiday (IOI14_holiday)	C++17	0 / 100	52 ms	39064 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5;
typedef long long int ll;
int di(int x){
	if(x<0)return (x-1)/2;
	else return x/2;
}
struct node{
	node *l = nullptr,*r = nullptr;
	int L = 0,R = 0;
	ll sum = 0;
	node(){}
	node(int _L,int _R) : L(_L),R(_R){}
	node(node *v):l(v->l),r(v->r),L(v->L),R(v->R),sum(v->sum){}
	void calc(){
		sum = 0;
		if(l)sum+=l->sum;
		if(r)sum+=r->sum;
	}
	ll query(int a,int b){
		if(a == L && b == R)return sum;
		int tm = di(L+R);
		if(a > tm && r)return r->query(a,b);
		else if(b<=tm && l)return l->query(a,b);
		else if(a<=tm && b>tm){
			ll res = 0;
			if(l)res+=l->query(a,tm);
			if(r)res+=r->query(tm+1,b);
			return res;
		}
		return 0;
	}
	void upd(int v,int val){
		if(L==R){sum+=val;return;}
		int tm = di(L+R);
		if(!l)l = new node(L,tm);
		if(!r)r = new node(tm+1,R);
		
		if(v <= tm)l->upd(v,val);
		else r->upd(v,val);
		calc();
	}
};
node *upd(node *v,int p,int val){
	if(v->L == v->R){
		node *res = new node(v);
		res->sum +=val;
		return res;
	}
	
	int tm = di(v->L + v->R);
	if(!v->l)v->l = new node(v->L,tm);
	if(!v->r)v->r = new node(tm+1,v->R);
	node *res = new node(v);
	if(p <= tm)res->l = upd(v->l,p,val);
	else res->r = upd(v->r,p,val);
	
	res->calc();
	return res;
}
long long int findMaxAttraction(int n, int start, int d, int a[]) {
	ll ans = 0;
	if(start==0){
		d++;
		vector<node*>val;
		val.push_back(new node(0,100));
		vector<int>cnt(101,0);
		for(int i=0;i<n;i++){
			d--;
			if(d<=0)break;
			cnt[a[i]]++;
			if(!i)val.back()->upd(a[i],a[i]);
			else val.push_back(upd(val.back(),a[i],a[i]));
			int tot = 0;
			ll sum = 0;
			for(int j=100;j>=0;j--){
				tot+=cnt[j];
				sum+=cnt[j] * j;
				if(tot-cnt[j] <= d && tot>=d){
					ans = max(ans,sum - (tot-d)*j);
				}
			}
		}
	}
	return ans;
}

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