Submission #91565

#	Time	Username	Problem	Language	Result	Execution time	Memory
91565		Alexa2001	Sparklers (JOI17_sparklers)	C++17	0 / 100	2 ms	676 KiB

sparklers

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1e5 + 5, lim = 1e9;

int X[Nmax];
int n, K, T;


struct Node
{
    Node *prv, *nxt;
    int val;
    int dprev, dnext;

    Node() {}

    Node(Node *_prv, Node *_nxt, int _val, int _dprev, int _dnext)
    {
        prv = _prv, nxt = _nxt; val = _val; dprev = _dprev; dnext = _dnext;
    }
};

Node *create_list()
{
    int i;
    Node *act = new Node(NULL, NULL, 1, -1, -1), *now, *special;
    special = act;

    for(i=2; i<=n; ++i)
    {
        if(X[i] == X[i-1])
            ++act -> val;
        else
        {
            now = new Node(act, NULL, 1, X[i] - X[i-1], -1);
            act -> dnext = X[i] - X[i-1];
            act -> nxt = now;
            act = now;
        }

        if(i == K) special = act;
    }
    return special;
}

void unite_front(Node *k)
{
    Node *u = k->prv;
    k->dprev = u->dprev;
    k->prv = u->prv;
    k->val += u->val;

    if(k->prv)
    {
        k->prv->nxt = k;
        k->prv->dnext = k->dprev;
    }
}

void unite_back(Node *k)
{
    Node *u = k->nxt;
    k->dnext = u->dnext;
    k->nxt = u->nxt;
    k->val += u->val;

    if(k->nxt)
    {
        k->nxt->prv = k;
        k->nxt->dprev = k->dnext;
    }
}

bool check(int S)
{
    Node *k = create_list();
    --k->val;

    int i;
    int rest;

    for(i=1; i<n; ++i)
    {
        if(k->val > 0)
        {
            rest = 2 * S * T;
        }
        else if(k->prv && k->dprev <= 2 * S * T)
        {
            rest = 2 * S * T - k->dprev;
            unite_front(k);
        }
        else if(k->nxt && k->dnext <= 2 * S * T)
        {
            rest = 2 * S * T - k->dnext;
            unite_back(k);
        }
        else return 0;
        --k->val;

        int R = rest;
        while(1)
        {
            if(k->prv && (!k->nxt || k->dprev < k->dnext))
            {
                if(k->dprev <= R)
                {
                    R -= k->dprev;
                    unite_front(k);
                    continue;
                }

                k->dprev -= R;
                k->prv->dnext -= R;
            }
            else if(k->nxt)
            {
                if(k->dnext <= R)
                {
                    R -= k->dnext;
                    unite_back(k);
                    continue;
                }

                k->dnext -= R;
                k->nxt->dprev -= R;
            }

            break;
        }
    }
    return 1;
}

int main()
{
 //   freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    int i;
    cin >> n >> K >> T;
    for(i=1; i<=n; ++i) cin >> X[i];

    int st = 0, dr = ceil(1.0 * lim / T / 2), mid;
    while(st <= dr)
    {
        mid = (st + dr) / 2;
        if(check(mid)) dr = mid-1;
            else st = mid+1;
    }
    cout << st << '\n';
    return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50