제출 #550595

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
550595		CSQ31	휴가 (IOI14_holiday)	C++17	0 / 100	86 ms	65536 KiB

holiday

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

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