oj.uz

Submission #247279

# Submission time Handle Problem Language Result Execution time Memory
247279 2020-07-11T08:35:13 Z uacoder123 Baloni (COCI15_baloni) C++14
40 / 100
 2000 ms 96004 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=lower_bound(all(arr[cur-1]),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
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47360 KB Output is correct
2 Correct 31 ms 47360 KB Output is correct
3 Correct 33 ms 47488 KB Output is correct
4 Correct 34 ms 47616 KB Output is correct
5 Execution timed out 2083 ms 90872 KB Time limit exceeded
6 Execution timed out 2088 ms 96004 KB Time limit exceeded
7 Execution timed out 2096 ms 87416 KB Time limit exceeded
8 Execution timed out 2089 ms 87200 KB Time limit exceeded
9 Execution timed out 2086 ms 89252 KB Time limit exceeded
10 Execution timed out 2093 ms 90748 KB Time limit exceeded