Submission #169686

#	Time	Username	Problem	Language	Result	Execution time	Memory
169686		stefdasca	Money (IZhO17_money)	C++14	0 / 100	2 ms	504 KiB

money

#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("Ofast")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9

using namespace std;

typedef long long ll;

int n, ans = 1, v[1000002], mx[1000002], mn[1000002];
bool iz[1000002];
set<int> s;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        cin >> v[i];
        mx[i] = max(mx[i-1], v[i]);
        if(i == 1)
            mn[i] = v[1];
        else
            mn[i] = min(mn[i-1], v[i]);
    }
    s.insert(v[1]);
    iz[v[1]] = 1;
    int i = 2;
    while(i <= n && v[i] >= v[i-1])
    {
        if(!iz[v[i]])
            iz[v[i]] = 1, s.insert(v[i]);
        ++i;
    }
    for(; i <= n; )
    {
        ++ans;
        if(v[i] >= mx[i])
        {
            int j = i+1;
            if(!iz[v[i]])
                iz[v[i]] = 1, s.insert(v[i]);
            while(j <= n && v[j] >= v[j-1])
            {
                if(!iz[v[j]])
                    iz[v[j]] = 1, s.insert(v[j]);
                ++j;
            }
            i = j;
        }
        else
        {
            if(v[i] < mn[i-1])
            {
                int j = i+1;
                if(!iz[v[i]])
                    iz[v[i]] = 1, s.insert(v[i]);
                while(j <= n && v[j] >= v[j-1] && v[j] <= mn[i-1])
                {
                    if(!iz[v[j]])
                        iz[v[j]] = 1, s.insert(v[j]);
                    ++j;
                }
                i = j;
            }
            else
            {
                int xx = i;
                while(i <= n && v[xx] == v[i])
                    ++xx;
                i = xx;
                if(i > n)
                    break;
                set<int> ::iterator it = s.lower_bound(v[i]);
                int val = *it;
                int j = i;
                while(j <= n && v[j] >= v[j-1] && v[j] <= val)
                {
                    if(!iz[v[j]])
                        iz[v[j]] = 1, s.insert(v[j]);
                    ++j;
                }
                i = j;
            }
        }
    }
    cout << ans;
    return 0;
}

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