Submission #60815

#	Time	Username	Problem	Language	Result	Execution time	Memory
60815		SpaimaCarpatilor	Railway Trip (JOI17_railway_trip)	C++17	100 / 100	502 ms	40392 KiB

railway_trip

#include<bits/stdc++.h>

using namespace std;

int N, K, Q, stk[100009], a[100009], lg[100009];
pair < int, int > dp[17][100009];

void init ()
{
    scanf ("%d %d %d", &N, &K, &Q);
    for (int i=1; i<=N; i++)
        scanf ("%d", &a[i]);
    int nr = 0;
    for (int i=1; i<=N; i++)
    {
        while (nr > 0 && a[stk[nr]] < a[i]) nr --;
        if (nr != 0) dp[0][i].first = stk[nr];
        else dp[0][i].first = i;
        stk[++nr] = i;
    }
    nr = 0;
    for (int i=N; i>=1; i--)
    {
        while (nr > 0 && a[stk[nr]] < a[i]) nr --;
        if (nr != 0) dp[0][i].second = stk[nr];
        else dp[0][i].second = i;
        stk[++nr] = i;
    }
}

void buildDp ()
{
    for (int i=2; i<=N; i++)
        lg[i] = lg[i >> 1] + 1;
    for (int i=1; i<=lg[N]; i++)
        for (int j=1; j<=N; j++)
        {
            auto f = dp[i - 1][j];
            dp[i][j].first = min (dp[i - 1][f.first].first, dp[i - 1][f.second].first);
            dp[i][j].second = max (dp[i - 1][f.first].second, dp[i - 1][f.second].second);
        }
}

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

init ();
buildDp ();
while (Q --)
{
    int L, R, ans = 0;
    scanf ("%d %d", &L, &R);
    if (L > R) swap (L, R);
    int x = L, y = L;
    for (int i=lg[R - L + 1]; i>=0; i--)
        if (max (dp[i][x].second, dp[i][y].second) < R)
        {
            int oldX = x, oldY = y;
            ans += 1 << i;
            x = min (dp[i][oldX].first, dp[i][oldY].first);
            y = max (dp[i][oldX].second, dp[i][oldY].second);
        }
    L = y;
    x = y = R;
    for (int i=lg[R - L + 1]; i>=0; i--)
        if (min (dp[i][x].first, dp[i][y].first) > L)
        {
            int oldX = x, oldY = y;
            ans += 1 << i;
            x = min (dp[i][oldX].first, dp[i][oldY].first);
            y = max (dp[i][oldX].second, dp[i][oldY].second);
        }
    printf ("%d\n", ans);
}

return 0;
}

Compilation message (stderr)

railway_trip.cpp: In function 'void init()':
railway_trip.cpp:10:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d %d", &N, &K, &Q);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:12:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d", &a[i]);
         ~~~~~~^~~~~~~~~~~~~
railway_trip.cpp: In function 'int main()':
railway_trip.cpp:54:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d", &L, &R);
     ~~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55