Submission #1179374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179374		Fikrat_Asadzadeh	Money (IZhO17_money)	C++20	0 / 100	7 ms	16040 KiB

money

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define FORI(i, n) for(ll i = 0; i < n; i++)
#define FOR(i, n) for(ll i = 1; i <= n; i++)
typedef vector < ll > vl; 
typedef set < ll > setl;
#define ff first
#define ss second    
#define all(v) v.begin(), v.end() 
#define pll pair<ll, ll> 
#define db double
#define nll cout << "\n"
#define nl "\n"
#define sync ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
ll poww(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1)res *= a;
        a *= a;
        b >>= 1;
    }
    return res;
}
const ll mod =  998244353;
const int sz = 1e6 + 5 ;
const long long imax = LLONG_MAX;
ll n, m, k, res, q, x, y;
ll a[sz], b[sz];
ll pref[sz];
struct fenwick{
    ll n;
    vl f;
    fenwick(ll sz){
        n = sz;
        f.resize(n + 5);
    }
    ll get(ll idx){
        ll res = 0;
        while(idx > 0){
            res += f[idx];
            idx -= (idx & -idx);
        }
        return res;
    }
    void update(ll idx, ll val){
        while(idx <= n){
            f[idx] += val;
            idx += (idx & -idx);
        }
    }
    ll query(ll l, ll r){
        if(l > r)return 0 ;
        return get(r) - get(l - 1);
    }
};
void solve(){
    cin >> n;
    FOR(i, n)cin >> a[i];
    vl used(1e6 + 5);
    fenwick f(1e6 );
    ll res = 0;
    FOR(i, n){
        if(!used[i]){
            vl cur;
            cur.push_back(a[i]);
            res++;
            used[i] = 1;
            for(ll j = i + 1; j <= n; j++){
                if(a[j] < a[j - 1] || f.query(a[j - 1] + 1, a[j] - 1) > 0)break;
                cur.push_back(a[j]);
                used[j] = 1;
            }
            for(auto x : cur)f.update(x, 1);
        }
    }
    cout << res;
}
//IOI rice hub
signed main(){      
    // freopen("input.txt","r",stdin);a
    // freopen("output.txt","w",stdout);
    sync;
    ll t = 1;
    // cin >> t;
    while(t--){
        solve();
    }   
}

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