Submission #180267

#	Time	Username	Problem	Language	Result	Execution time	Memory
180267		mat_v	Money (IZhO17_money)	C++14	100 / 100	219 ms	15100 KiB

money

#include <bits/stdc++.h>

using namespace std;


int n;
int niz[1000005];
int bit[1000005];
int upit(int x){
    int res = 0;
    while(x > 0){
        res += bit[x];
        x -= (x&-x);
    }
    return res;
}
void add(int x){
    while(x <= 1000000){
        bit[x]++;
        x += (x&-x);
    }
}
int query(int l, int r){
    if(l > r)return 0;
    return upit(r) - upit(l - 1);
}
void ubaci(int l, int r){
    for(int i=l; i<=r; i++){
        add(niz[i]);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n;
    for(int i=1; i<=n; i++)cin >> niz[i];
    int br = 1;
    int last = 1;
    int res = 1;
    while(br <= n){
        if(niz[br] < niz[br - 1]){
            ubaci(last, br - 1);
            last = br;
            br++;
            res++;
            continue;
        }
        //cout << br << " " << last << endl;
        if(query(niz[last] + 1, niz[br] - 1) >= 1){
            ubaci(last, br - 1);
            last = br;
            br++;
            res++;
        }
        else br++;
    }
    cout << res << endl;
    return 0;
}

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