Submission #342801

#	Time	Username	Problem	Language	Result	Execution time	Memory
342801		ivan_tudor	Money (IZhO17_money)	C++14	100 / 100	227 ms	15084 KiB

money

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 6;
int v[N];
int aib[N];
void upd(int poz, int val){
  for(int i = poz; i < N ; i+= i&(-i))
    aib[i] += val;
}
int query(int poz){
  int ans = 0;
  for(int i= poz; i > 0; i-= i&(-i))
    ans+=aib[i];
  return ans;
}
multiset<int> ms;
void dbg(){
  cerr<<ms.size()<<"\n";
  for(auto x: ms)
    cerr<<x<<" ";
  cerr<<"\nok\n";
}

const int SIZE=1<<10;
char buffer[SIZE];
int point=SIZE;
inline char adv(){
  if(point==SIZE){
    fread(buffer,1,SIZE,stdin);
    point=0;
  }
  return buffer[point++];
}
inline int read(){
  char c;
  int x=0,sgn=1;
  c=adv();
  while(isdigit(c)==false && c!='-')
    c=adv();
  while(c=='-'){
    sgn*=-1;
    c=adv();
  }
  while(isdigit(c)){
    x=x*10+c-'0';
    c=adv();
  }
  return x*sgn;
}
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];
    upd(v[i], 1);
  }
  int ans = 0;
  for(int i= n; i>=1;){
    int j = i;
    ans++;

    while(j>=1 && v[j] == v[i]){
      upd(v[i], -1);
      j--;
    }
    while(j>=1 && query(v[i] - 1) - query(v[j]) == 0){
      upd(v[j], -1);
      j--;

    }
    i = j;
  }
  cout<<ans;
  return 0;
}

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