Submission #533252

#	Time	Username	Problem	Language	Result	Execution time	Memory
533252		kebine	Money (IZhO17_money)	C++17	0 / 100	1 ms	332 KiB

money

#include <bits/stdc++.h>
using namespace std;
 
typedef int ll;
typedef double db;
#define pairll pair<ll,ll>
#define lpairll pair<ll,pairll>
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define repp(i,a,b) for(ll i = (a); i <= (b); i++)
#define repm(i, a, b) for (ll i = (a); i >= (b); i--)
#define repz(i, a, b) for (ll i = (a); i < (b); i++)
 
const long long MOD = 1e9+7, N = 1e6 + 5, M = 1e3+5, INF = 1e9; 

ll tc = 1, n, m,k,ar[N];
string s, ye = "YES", no = "NO", nu;
vector<pairll> ed[2], blu;

void fastt(){  
  ios_base::sync_with_stdio(0); 
  cin.tie(NULL);
  cout.tie(NULL);  
}

void input(){
  cin >> n;
  repp(i,1,n) cin >> ar[i];
} 

void solve(){
  set<ll> stz;
  ll ans = 1, l = 1, pre;
  while(l <= n && ar[l] >= ar[l-1]){
    stz.insert(ar[l]);
    l++;
  }
  repp(i,l,n){
    if(ar[i] < ar[i-1]){
      pre = i;
      stz.insert(ar[i]);
      ans++;
    }
    else{
      auto it = stz.lower_bound(ar[i-1]);
      it++;
      if(it == stz.end() || *it >= ar[i]) stz.insert(ar[i]);
      else{
        ans++;
        stz.insert(ar[i]);
      }
    }
  }
  cout << ans << endl;
}

int main(){
  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);
  fastt();
  while(tc--){
    input();
    solve();
  }
}

/*
3
1 2 3

1 2 3

5
2 8 6 3 1
1 2 3 6 8

(n-1)/2

*/

Compilation message (stderr)

money.cpp: In function 'void solve()':
money.cpp:36:22: warning: variable 'pre' set but not used [-Wunused-but-set-variable]
   36 |   ll ans = 1, l = 1, pre;
      |                      ^~~

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