Submission #94415

#	Time	Username	Problem	Language	Result	Execution time	Memory
94415		Kastanda	Money (IZhO17_money)	C++11	100 / 100	264 ms	18808 KiB

money

#include<bits/stdc++.h>
using namespace std;
const int N = 1000006;
int n, cnt, A[N], C[N], nxt[N];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &A[i]), C[A[i]] ++;
    C[N - 1] ++;
    for (int i = N - 2; i; i--)
    {
        nxt[i] = i + 1;
        while (!C[nxt[i]])
            nxt[i] = nxt[nxt[i]];
    }
    for (int i = n; i;)
    {
        int used = 0;
        int l = i - 1;
        while (l)
        {
            C[A[l + 1]] --;
            if (A[l] > A[l + 1])
                break;
            if (A[l] == A[l + 1])
            {
                l --;
                continue;
            }
            while (!C[nxt[A[l]]])
                nxt[A[l]] = nxt[nxt[A[l]]];
            if (nxt[A[l]] < A[l + 1])
                break;
            if (nxt[A[l]] == A[l + 1] && used)
                break;
            used = 1;
            l --;
        }
        i = l;
        cnt ++;
    }
    return !printf("%d", cnt);
}

Compilation message (stderr)

money.cpp: In function 'int main()':
money.cpp:7:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
money.cpp:9:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i]), C[A[i]] ++;
         ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 55 / 55