Submission #342789

#	Time	Username	Problem	Language	Result	Execution time	Memory
342789		ivan_tudor	Money (IZhO17_money)	C++14	45 / 100	1588 ms	58112 KiB

money

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 6;
int v[N];
multiset<int> ms;
void dbg(){
  cerr<<ms.size()<<"\n";
  for(auto x: ms)
    cerr<<x<<" ";
  cerr<<"\nok\n";
}
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n;
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>v[i];
    ms.insert(v[i]);
  }
  int ans = 0;
  for(int i= n; i>=1;){
    int j = i;
    ans++;
    while(j>=1 && v[j] == v[i]){
      ms.erase(ms.find(v[i]));
      j--;
    }
    multiset<int>::iterator itr = ms.lower_bound(v[i]);
    if(itr != ms.begin()){
      itr --;
      while(j>=1 && v[j] == (*itr)){
        j--;
        if(itr == ms.begin()){
          ms.erase(itr);
          break;
        }
        multiset<int>::iterator newitr = itr;
        newitr --;
        ms.erase(itr);
        itr = newitr;
      }
    }
    i = j;
  }
  cout<<ans;
  return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 0 / 55