Submission #1024134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024134		serkanrashid	Holiday (IOI14_holiday)	C++14	0 / 100	96 ms	11952 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>

using namespace std;

struct Node
{
    int br;
    long long sum;
    Node(){};
    Node(int br, long long sum) : br(br), sum(sum) {}
};

const int maxn = 1e5+5;

int n,start,d,pl,pr,ost;

Node tree[4*maxn];
int ql,qr,val;

long long atr[maxn];
long long ans = 0;

Node Merge(Node n1, Node n2)
{
    return {n1.br+n2.br , n1.sum+n2.sum};
}

void make_clear(int v, int l, int r)
{
    if(l==r)
    {
        tree[v] = {0,0};
        if(r==0) tree[v] = {1,0};
        return;
    }
    int mid = (l+r)/2;
    make_clear(v*2+0,l,mid+0);
    make_clear(v*2+1,mid+1,r);
    tree[v] = Merge(tree[v*2+0],tree[v*2+1]);
}

void pre_clear()
{
    ans = 0;
    make_clear(1,0,n);
    pl = pr = 0;

}

long long query(int v, int l, int r, int ost)
{
    if(ost==0) return 0;
    if(tree[v].br <= ost) return tree[v].sum;
    if(l == r) return (tree[v].sum / tree[v].br) * ost;

    int mid = (l+r)/2;
    if(tree[v*2+1].br > ost) query(v*2+1,mid+1,r,ost);
    return query(v*2+0,l,mid+0,ost-tree[v*2+1].br) + tree[v*2+1].sum;
}

void update(int v, int l, int r)///map
{
    if(l==r)
    {
        if(val==1)
        {
            tree[v].br++;
            tree[v].sum += r;
        }
        else
        {
            tree[v].br--;
            tree[v].sum -= r;
        }
        return;
    }
    int mid = (l+r)/2;
    if(qr<=mid) update(v*2+0,l,mid+0);
    else update(v*2+1,mid+1,r);
    tree[v] = Merge(tree[v*2+0],tree[v*2+1]);
}

void p_activate(int l, int r)
{
    while(l<pl)
    {
        pl--;
        val = 1;
        ql = qr = atr[pl];///map
        update(1,0,n);
    }
    while(pr<r)
    {
        pr++;
        val = 1;
        ql = qr = atr[pr];///map;
        update(1,0,n);
    }
    while(pl<l)
    {
        val = -1;
        ql = qr = atr[pl];///map
        update(1,0,n);
        pl++;
    }
    while(r<pr)
    {
        val = -1;
        ql = qr = atr[pr];///map
        update(1,0,n);
        pr--;
    }
}

void divide(int l, int r, int optl, int optr)
{
    if(l>r) return;
    int mid = (l+r)/2;
    pair<long long,int> best = {-1,-1};
    for(int i = optl; i <= optr; i++)
    {
        int ost = d - 2*(mid-start);///mozhe da se optimizira FOR
        if(ost<0) continue;
        p_activate(i,mid);

        long long pom = query(1,0,n,ost);
        if(pom>best.first) best = {pom,i};
    }
    ans = max(ans,best.first);
    int opt = best.second;

    if(opt == -1) divide(l,mid-1,optl,optr);
    else
    {
        divide(l,mid-1,optl,opt);
        divide(mid+1,r,opt,optr);
    }
}

long long solve(int sti, int di)
{
    start = sti;
    d = di;
    pre_clear();
    divide(start,n-1,0,start);
    return ans;
}

long long int findMaxAttraction(int N, int start, int d, int attraction[])
{
    n = N;
    for(int i = 0; i < n; i++) atr[i] = attraction[i];

    long long res = solve(start,d);
    reverse(atr+0,atr+n);
    res = max(res,solve(n-1-start,d));

    return res;
}

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