Submission #755010

#	Time	Username	Problem	Language	Result	Execution time	Memory
755010		AngusRitossa	Holiday (IOI14_holiday)	C++14	24 / 100	153 ms	41900 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int lef[1000010], righ[1000010], am[1000010];
ll val[1000010];
int upto;
void update(int node, int oldcurr, int curr, int cstart = 0, int cend = 1e9+10)
{
	if (cstart == cend)
	{
		am[curr] = am[oldcurr]+1;
		val[curr] = ((ll)am[curr]) * ((ll)cstart);
		return;
	}
	int mid = (cstart+cend)/2;
	if (node <= mid) 
	{
		lef[curr] = ++upto;
		righ[curr] = righ[oldcurr];
		update(node, lef[oldcurr], lef[curr], cstart, mid);
	}
	else
	{
		righ[curr] = ++upto;
		lef[curr] = lef[oldcurr];
		update(node, righ[oldcurr], righ[curr], mid+1, cend);
	}
	am[curr] = am[lef[curr]] + am[righ[curr]];
	val[curr] = val[lef[curr]] + val[righ[curr]];
}
ll query(int amt, int oldcurr, int curr, int cstart = 0, int cend = 1e9+10)
{
	if (amt >= am[curr] - am[oldcurr]) return val[curr] - val[oldcurr];
	else if (cstart == cend)
	{
		ll mult = min(amt, am[curr]-am[oldcurr]);
		return mult*(ll)cstart;
	}
	int mid = (cstart+cend)/2;
	if (am[righ[curr]] - am[righ[oldcurr]] >= amt)
	{
		return query(amt, righ[oldcurr], righ[curr], mid+1, cend);
	}
	else
	{
		int newam = amt - (am[righ[curr]] - am[righ[oldcurr]]);
		ll val2 = val[righ[curr]] - val[righ[oldcurr]];
		return val2 + query(newam, lef[oldcurr], lef[curr], cstart, mid);
	}
} 
int* rootat;
int otherarray[100010];
priority_queue<ll> pq;
ll mx;
ll findMaxAttraction2(int n, int start, int d, int attraction[]) {
    assert(!start);
    int at = d/2;
    int moves = at*2-1;
    ll sum = 0;
    for (int i = 0; i < at; i++)
    {
    	sum += attraction[i];
    	pq.push(-attraction[i]);
    }
    mx = sum;
    for (int i = at; i < n; i++)
    {
    	moves += 2;
    	pq.push(-attraction[i]);
    	sum += attraction[i];
    	while (moves > d && pq.size())
    	{
    		sum += pq.top();
    		pq.pop();
    		moves--;
    	}
    	//printf("%d %d\n", pq.size(), mx);
    	mx = max(mx, sum);
    }
    return mx;
}

ll findMaxAttraction(int n, int start, int d, int attraction[]) {
	rootat = otherarray+1;
	if (!start) return findMaxAttraction2(n, start, d, attraction);
	for (int i = 0; i < n; i++)
	{
		rootat[i] = ++upto;
		update(attraction[i], rootat[i-1], rootat[i]);
	}
    for (int s = 0; s <= start; s++)
    {
    	int dist = start-s-1;
    	for (int e = s; e < n; e++)
    	{
    		dist++;
    		int allowed = d-dist;
    		if (allowed <= 0) continue;
    		ll sum = query(allowed, rootat[s-1], rootat[e]);
    		mx = max(mx, sum);
    	}
    }
   // printf("\n");
    for (int e = start; e < n; e++)
    {
    	int dist = e-start-1;
    	for (int s = e; s >= 0; s--)
    	{
    		dist++;
    		int allowed = d-dist;
    		if (allowed <= 0) continue; 
    		ll sum = query(allowed, rootat[s-1], rootat[e]);
    		mx = max(mx, sum);
    	}
    }
    return mx;
}

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