Submission #46990

#	Time	Username	Problem	Language	Result	Execution time	Memory
46990		SpaimaCarpatilor	Sparklers (JOI17_sparklers)	C++17	100 / 100	79 ms	29964 KiB

sparklers

#include<bits/stdc++.h>

using namespace std;

int L, R, N, K, T, x[100009], stk[100009];
long long v[100009], mi[100009], ma[100009];
pair < int, long long > lft[100009], rgt[100009];

bool firstPart ()
{
    int nr = 0;
    for (int i=1; i<=K; i++)
    {
        while (nr > 0 && v[stk[nr]] < v[i])
            mi[nr - 1] = min (mi[nr - 1], mi[nr]), nr --;
        if (nr == 0) L = i;
        else lft[i] = {stk[nr], mi[nr]};
        stk[++nr] = i, mi[nr] = v[i];
    }
    nr = 0;
    for (int i=N; i>=K; i--)
    {
        while (nr > 0 && v[stk[nr]] > v[i])
            ma[nr - 1] = max (ma[nr - 1], ma[nr]), nr --;
        if (nr == 0) R = i;
        else rgt[i] = {stk[nr], ma[nr]};
        stk[++nr] = i, ma[nr] = v[i];
    }
    int l = K, r = K;
    bool change = 1;
    while (change)
    {
        change = 0;
        if (l != L && lft[l].second >= v[r])
            l = lft[l].first, change = 1;
        if (r != R && rgt[r].second <= v[l])
            r = rgt[r].first, change = 1;
    }
    return (l == L && r == R);
}

bool secondPart ()
{
    if (v[1] < v[N]) return 0;
    int nr = 0;
    for (int i=K; i>=1; i--)
    {
        while (nr > 0 && v[stk[nr]] <= v[i])
            mi[nr - 1] = min (mi[nr - 1], mi[nr]), nr --;
        if (nr == 0) L = i;
        else lft[i] = {stk[nr], mi[nr]};
        stk[++nr] = i, mi[nr] = v[i];
    }
    nr = 0;
    for (int i=K; i<=N; i++)
    {
        while (nr > 0 && v[stk[nr]] >= v[i])
            ma[nr - 1] = max (ma[nr - 1], ma[nr]), nr --;
        if (nr == 0) R = i;
        else rgt[i] = {stk[nr], ma[nr]};
        stk[++nr] = i, ma[nr] = v[i];
    }
    int l = 1, r = N;
    bool change = 1;
    while (change)
    {
        change = 0;
        if (l != L && lft[l].second >= v[r])
            l = lft[l].first, change = 1;
        if (r != R && rgt[r].second <= v[l])
            r = rgt[r].first, change = 1;
    }
    return (l == L && r == R);
}

bool ok (int S)
{
    for (int i=1; i<=N; i++)
        v[i] = x[i] - 2LL * i * S * T;
    if (!firstPart ()) return 0;
    if (!secondPart ()) return 0;
    return 1;
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d %d", &N, &K, &T);
for (int i=1; i<=N; i++)
    scanf ("%d", &x[i]);
int p = 0, u = (x[N] - x[1]) / T + 1, mij, ras = -1;
while (p <= u)
{
    mij = (p + u) >> 1;
    if (ok (mij)) ras = mij, u = mij - 1;
    else p = mij + 1;
}
printf ("%d\n", ras);
return 0;
}

Compilation message (stderr)

sparklers.cpp: In function 'int main()':
sparklers.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d %d %d", &N, &K, &T);
 ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:92:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &x[i]);
     ~~~~~~^~~~~~~~~~~~~

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