Submission #791220

#	Time	Username	Problem	Language	Result	Execution time	Memory
791220		AndiR	Money (IZhO17_money)	C++14	0 / 100	1 ms	340 KiB

money

#include <iostream>

using namespace std;
const int Nmax=1000000;

int n, aib[Nmax+1], v[Nmax];
void aib_add(int pos){
    for (int i=pos; i<=Nmax; i+=i&-i)
        aib[i]++;
}
int aib_sum(int l, int r){
    int s;
    for (int i=r; i>0; i-=i&-i)
        s+=aib[i];
    for (int i=l-1; i>0; i-=i&-i)
        s-=aib[i];
    return s;
}
int main()
{
    cin>>n;
    for (int i=0; i<n; i++)
        cin>>v[i];
    int mn=0, mx=0, sol=1;
    for (int i=1; i<n; i++){
        if (v[i]>=v[mx]){
            mx=i;
            if (v[mx]-v[mn]>=2)
                if (aib_sum(v[mn]+1, v[mx]-1)>0){
                    sol++;
                    for (int j=mn; j<i; j++)
                        aib_add(v[j]);
                    mn=i;
                }
        }
        else{
            sol++;
            for (int j=mn; j<i; j++)
                aib_add(v[j]);
            mx=mn=i;
        }
    }
    cout<<sol;
    return 0;
}

Compilation message (stderr)

money.cpp: In function 'int aib_sum(int, int)':
money.cpp:16:10: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
   16 |         s-=aib[i];
      |         ~^~~~~~~~
money.cpp: In function 'int main()':
money.cpp:14:10: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
   14 |         s+=aib[i];
      |         ~^~~~~~~~
money.cpp:12:9: note: 's' was declared here
   12 |     int s;
      |         ^

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