oj.uz

답안 #247230

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
247230 2020-07-11T08:16:19 Z uacoder123 Baloni (COCI15_baloni) C++14
40 / 100
 2000 ms 96120 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;
      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(in);
            while(cur!=1)
            {
              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

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 47352 KB Output is correct
2 Correct 32 ms 47488 KB Output is correct
3 Correct 32 ms 47488 KB Output is correct
4 Correct 35 ms 47616 KB Output is correct
5 Execution timed out 2083 ms 90720 KB Time limit exceeded
6 Execution timed out 2096 ms 96120 KB Time limit exceeded
7 Execution timed out 2089 ms 87544 KB Time limit exceeded
8 Execution timed out 2087 ms 87160 KB Time limit exceeded
9 Execution timed out 2093 ms 89208 KB Time limit exceeded
10 Execution timed out 2102 ms 90744 KB Time limit exceeded