oj.uz

Submission #247277

# Submission time Handle Problem Language Result Execution time Memory
247277 2020-07-11T08:34:29 Z uacoder123 Baloni (COCI15_baloni) C++14
100 / 100
 1311 ms 96056 KB 
     #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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47360 KB Output is correct
2 Correct 32 ms 47488 KB Output is correct
3 Correct 36 ms 47616 KB Output is correct
4 Correct 33 ms 47616 KB Output is correct
5 Correct 1052 ms 90900 KB Output is correct
6 Correct 1269 ms 96056 KB Output is correct
7 Correct 986 ms 87552 KB Output is correct
8 Correct 913 ms 87076 KB Output is correct
9 Correct 1006 ms 89276 KB Output is correct
10 Correct 1311 ms 90744 KB Output is correct