Submission #685098

#	Time	Username	Problem	Language	Result	Execution time	Memory
685098		speedyArda	Money (IZhO17_money)	C++14	100 / 100	1238 ms	58064 KiB

money

#include "bits/stdc++.h"
using namespace std;
const int MAXN = 1e6+5;
int pos[MAXN];
int in[MAXN];
int main() 
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> in[i];
    in[0] = 0;
    set<int> last; // so that we don't have duplicates
    int idx = 1, res = 1; // First segment
    while(idx <= n && in[idx] >= in[idx - 1])
    {
        last.insert(in[idx]);
        idx++;
    }
    if(idx > n)
    {
        cout << res << "\n";
        return 0;
    }

    for(idx; idx <= n; idx++)
    {
        int endidx = idx + 1;
        int firstnum = 0;
        if(last.lower_bound(in[idx]) != last.end())
        {
            firstnum = *(last.lower_bound(in[idx]));
        }
        int secondnum = 1e9;
        if(last.upper_bound(in[idx]) != last.end())
            secondnum = *(last.upper_bound(in[idx]));
        last.insert(in[idx]);
        idx++;
        while(idx <= n && in[idx] >= in[idx-1] && in[idx] <= secondnum)
        {
            last.insert(in[idx]);
            idx++;
        }
        res++; // New range
        idx--;
    }

    cout << res << "\n";
    
}

Compilation message (stderr)

money.cpp: In function 'int main()':
money.cpp:26:9: warning: statement has no effect [-Wunused-value]
   26 |     for(idx; idx <= n; idx++)
      |         ^~~
money.cpp:28:13: warning: unused variable 'endidx' [-Wunused-variable]
   28 |         int endidx = idx + 1;
      |             ^~~~~~
money.cpp:29:13: warning: variable 'firstnum' set but not used [-Wunused-but-set-variable]
   29 |         int firstnum = 0;
      |             ^~~~~~~~

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