Submission #1113639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113639		jnjwnwnw	Money (IZhO17_money)	C++17	0 / 100	10 ms	63056 KiB

money

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
#define fff(i, a, b) for(int i = a; i < b; i++)

class SegmentTree // range set value, range query for sum segtree, can be easily modified for other things
{
    private:
        int n;
        vector<long long> segtree;
        vector<long long> lazy;
    public:
        void init(int sz)
        {
            n = sz;
            segtree.resize(1 + 4 * sz);
            lazy.resize(1 + 4 * sz);
        }
        void lz(int node, int L, int R)
        {
            segtree[node] += lazy[node];
            if(L != R)
            {
                lazy[node << 1] += lazy[node];
                lazy[node << 1|1] += lazy[node];
            }
            lazy[node] = 0;
        }
        void build(int node, int L, int R, vector<int> &v)
        {
            if(L == R)
            {
                segtree[node] = v[L];
                return;
            }
            int mid = (L + R) / 2;
            build(node << 1, L, mid, v);
            build(node << 1|1, mid+1, R, v);
            segtree[node] = segtree[node << 1] + segtree[node << 1|1];
        }
        void update(int node, int L, int R, int Lq, int Rq, int val)
        {
            if(lazy[node])
                lz(node, L, R);
            if(R < Lq || L > Rq)
                return;
            if(Lq <= L && R <= Rq)
            {
                lazy[node] = val;
                lz(node, L, R);
                return;
            }
            int mid = (L + R) / 2;
            update(node << 1, L, mid, Lq, Rq, val);
            update(node << 1|1, mid+1, R, Lq, Rq, val);
            segtree[node] = segtree[node << 1] + segtree[node << 1|1];
        }
        long long query(int node, int L, int R, int Lq, int Rq)
        {
            if(lazy[node])
                lz(node, L, R);
            if(R < Lq || L > Rq)
                return 0;
            if(Lq <= L && R <= Rq)
                return segtree[node];
            int mid = (L + R) / 2;
            return query(node << 1, L, mid, Lq, Rq) + query(node << 1|1, mid+1, R, Lq, Rq);
        }
};

SegmentTree st;

#define N 1000006
int n;
int A[N];
int main(){
    cin >> n;
    fff(i, 0, n){
        cin >> A[i];
    }
    st.init(N);
    int num_segs = 1;
    int l = 0;
    fff(i, 0, n-1){
        // see if a segment split happens between i and i+1
        // current segment is from l to i and possible i+1
        int a = A[i], b = A[i+1];
        bool splt = 0;
        if (a > b || (b-a > 1 && st.query(1, 0, N-1, a+1, b-1))){
            // values in between a and b exist, or a >b, also problematic
            fff(j, l, i+1){
                st.update(1, 0, N-1, A[j], A[j], 1);
            }
            l = i+1;
            num_segs++;
        }
    }
    cout << num_segs << endl;
}

Compilation message (stderr)

money.cpp: In function 'int main()':
money.cpp:90:14: warning: unused variable 'splt' [-Wunused-variable]
   90 |         bool splt = 0;
      |              ^~~~

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