제출 #340034

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
340034		Sprdalo	Money (IZhO17_money)	C++17	45 / 100	1581 ms	98284 KiB

money

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;

//Slozenost O(log n)

template<class T, int size>
struct fenwick {
    T a[size];
    /* precondition: pos > 0 */
    void add(int pos, const T& val) {
        while (pos < size) {
            a[pos] += val;
            pos += pos & -pos;
        }
    }
    T sum(int pos) {
        T ret = T();
        while (pos > 0) {
            ret += a[pos];
            pos -= pos & -pos;
        }
        return ret;
    }
};
fenwick<int, 131072*16> drvo;
 
map<int, int> m;
signed main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    cerr.tie(nullptr);    
 
    int n;
    cin >> n;
 
    vi a(n);
    set<int> s;
    for (auto& i : a){
        cin >> i;
        s.insert(i);
    }
 
    int cur = 1;
    for (auto& i : s){
        m[i] = cur++;
    }
 
    for (auto& i : a){
        i = m[i];
    }
 
    int l = 0, r = 1, sol = 1;
    while(1){
        if (r == n) break;
 
        if (a[r] < a[r-1]){
 
            for (int i = l; i < r; ++i)
                drvo.add(a[i], 1);
 
            ++sol;
            l = r;
            r++;
            drvo.add(a[l], 1);
            continue;
        }
 
        if (a[l]+1 > a[r]-1){
            ++r;
            continue;
        }
 
        int x = drvo.sum(a[r]-1) - drvo.sum(a[l]);
        if (!x){
            ++r;
            continue;
        }
 
        for (int i = l; i < r; ++i)
            drvo.add(a[i], 1);
        l = r;
        ++sol;
        ++r;
    }
 
    cout<< sol << '\n';
}

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