Submission #247277

#	Time	Username	Problem	Language	Result	Execution time	Memory
247277		uacoder123	Baloni (COCI15_baloni)	C++14	100 / 100	1311 ms	96056 KiB

baloni

     #include <bits/stdc++.h>
    using namespace std;
    #define F first
    #define S second
    #define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
    #define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
    #define all(x) (x).begin(), (x).end()
    #define sz(x) int(x.size())
    #define mp(i,a) make_pair(i,a)
    #define pb(a) push_back(a)
    #define bit(x,b) (x&(1LL<<b))
     
    typedef long long int lli;
    typedef pair <lli,lli> ii;
    typedef pair <lli,ii> iii;
    typedef vector <lli> vi;
    set<int> arr[1000001];
    int arr1[1000001],ch[1000001]={},c=0;
    int main()
    {
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
      int test=1,co=0;
      for(;test>0;--test)
      {
        int n;
        cin>>n;
        for(int i=0;i<n;++i)
        {
          cin>>arr1[i];
          arr[arr1[i]].insert(i);
        }
        for(int i=0;i<n;++i)
        {
          if(ch[i]==0)
          {
            c++;
            int cur=arr1[i],in=i;
            ch[i]=1;
            arr[cur].erase(arr[cur].begin());
            while(cur!=1)
            {
              co++;
              auto it=arr[cur-1].lower_bound(in);
              if(it==arr[cur-1].end())
                break;
              else
              {
                in=(*it);
                cur--;
                ch[in]=1;
                arr[cur].erase(it);
              }
            }
          }
        }
        cout<<c<<endl;
      }
      return(0);
    }

• Subtask 1: 100 / 100