Cod sursa(job #2447766)

Utilizator vladadAndries Vlad Andrei vladad Data 14 august 2019 15:36:52
Problema Range minimum query Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
ull n, fr[500001], v[500100], x, k, fr2[500001];
set<ull>s;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        ull x;
        cin>>x;
        fr[x]++;
        if(x!=1)
        {
            if(fr[x]<=3)
                v[++k]=x;
        }
        else
        {
            if(fr[x]<=2)
                v[++k]=x;
        }
    }
    for(int i=1; i<=k; i++)
    {
        if(v[i]!=1)
        {
            if(!fr2[v[i]])
            {
                s.insert(v[i]);
                fr[v[i]]--;
                fr2[v[i]]++;
            }
            else
            {
                if(!fr2[v[i]-1]) s.insert(v[i]-1), fr2[v[i]-1]++;
                else if(!fr2[v[i]+1]) s.insert(v[i]+1);
                fr[v[i]]--;
            }

            if(fr[v[i]]>=2)
            {
                s.insert(v[i]+1);
                s.insert(v[i]-1);
                fr2[v[i]+1]++;
                fr2[v[i]-1]++;
            }
            else
            {
                if(fr[v[i]]==1)
                {
                    if(!fr2[v[i]-1])
                        s.insert(v[i]-1), fr2[v[i]-1]++;
                    else
                        s.insert(v[i]+1), fr2[v[i]+1]++;

                }
            }
        }
        else if(v[i]==1)
        {
            s.insert(v[i]);
            fr[v[i]]--;
            fr2[v[i]]++;
            if(fr[v[i]]) s.insert(v[i]+1), fr2[v[i]+1]++;
        }
    }
    cout<<s.size();
    return 0;
}