Submission #36148

#	Time	Username	Problem	Language	Result	Execution time	Memory
36148		Kanvie	Money (IZhO17_money)	C++14	100 / 100	413 ms	6080 KiB

money

#include<bits/stdc++.h>
using namespace std;
int f[1000001]={0},n,ans=0,trc=0,trc_M,x;
void update(int pos,int value)
{
    for (int i=pos; i<=1000000; i+=(i&(-i)))f[i]+=value;
}
int get(int pos)
{
    int r=0;
    for (int i=pos; i>=1; i-=(i&(-i)))r+=f[i];
    return r;
}
int gets(int ll, int rr)
{
    return get(rr)-get(ll-1);
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);
    stack<int>q;
    memset(f,0,sizeof(f));
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d",&x);
        if(ans==0)
        {
            q.push(x);
            ans++;
            trc=x;
            trc_M=x;
            continue;
        }
        if(x<trc||(trc_M+1<x&&gets(trc_M+1,x-1)>0))
        {
            ans++;
            trc=x;
            trc_M=x;
            while(!q.empty())
            {
                update(q.top(),1);
                q.pop();
            }
            q.push(x);
            continue;
        }
        trc=x;
        q.push(x);
    }
    printf("%d",ans);
}

Compilation message (stderr)

money.cpp: In function 'int main()':
money.cpp:23:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
money.cpp:26:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
                       ^

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