Submission #937387

#	Time	Username	Problem	Language	Result	Execution time	Memory
937387		vgoofficial	Growing Trees (BOI11_grow)	C++14	0 / 100	1058 ms	12164 KiB

grow

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pi = pair<int, int>;
#define add push_back 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define f first
#define s second
#define trav(a,x) for (auto& a: x)
ll mod = 1000000007;
// Overload for printing vectors
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
    os << "[ ";
    for(const auto& elem : vec) {
        os << elem << " ";
    }
    os << "]";
    return os;
}

// Overload for printing sets
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& s) {
    os << "{ ";
    for(const auto& elem : s) {
        os << elem << " ";
    }
    os << "}";
    return os;
}
// Overload for printing maps
template<typename K, typename V>
std::ostream& operator<<(std::ostream& os, const std::map<K, V>& m) {
    os << "{ ";
    for(const auto& pair : m) {
        os << pair.first << " : " << pair.second << ", ";
    }
    os << "}";
    return os;
}
ll inf = 1e15;
struct SegTree {
    int n;
    vector<ll> minTree, maxTree, upd;
    vector<int> begin, end;
    SegTree(int nn): n(nn) {
        while(n!=(n&(-n))) n++;
        minTree.resize(2*n, inf);
        maxTree.resize(2*n, inf);
        upd.resize(2*n);
        begin.resize(2*n);
        end.resize(2*n);
        FOR(i, n, 2*n) begin[i]=end[i]=i-n;
        ROF(i, 1, n) {
            begin[i]=begin[2*i];
            end[i]=end[2*i+1];
        }
    }
    void push(int i) { 
        if(upd[i]!=0) {
            minTree[2*i]+=upd[i];
            maxTree[2*i]+=upd[i];
            minTree[2*i+1]+=upd[i];
            maxTree[2*i+1]+=upd[i];
            upd[2*i]+=upd[i];
            upd[2*i+1]+=upd[i];
            upd[i]=0;
        }
    }
    void build(vector<ll> heights) {
        F0R(i, heights.size()) {
            minTree[i+n]=maxTree[i+n]=heights[i];
        }
        ROF(i, 1, n) {
            minTree[i]=min(minTree[2*i], minTree[2*i+1]);
            maxTree[i]=max(maxTree[2*i], maxTree[2*i+1]);
        }
    }

    int query(ll min, ll max, int i=1) {
        if(minTree[i]>=min&&maxTree[i]<=max&&minTree[i]<=maxTree[i]) {
            return end[i]-begin[i]+1;
        }
        push(i);
        int count = 0;
        if(minTree[2*i]<=max&&maxTree[2*i]>=min) {
            count+=query(min, max, 2*i);
        }
        if(minTree[2*i+1]<=max&&maxTree[2*i+1]>=min) {
            count+=query(min, max, 2*i+1);
        }
        return count;
    }
    void apply(int count, ll minHeight) {
        int startIndex = 1;
        while(startIndex<n) {
            push(startIndex);
            if(maxTree[startIndex*2]>=minHeight) {
                startIndex*=2;
            } else {
                startIndex*=2;
                startIndex++;
            }
        }
        startIndex-=n;
        int endIndex = startIndex+count-1;
        if(endIndex>=n) {
            rangeAdd(startIndex, n-1);
        } else {
            explore(endIndex);
            int target = minTree[endIndex+n];
            int minusEnd = 1;
            while(minusEnd<n) {
                push(minusEnd);
                if(minTree[2*minusEnd+1]<=target-1) {
                    minusEnd*=2;
                    minusEnd++;
                } else {
                    minusEnd*=2;
                }
            }
            minusEnd-=n;
            count-=minusEnd-startIndex+1;
            
            rangeAdd(startIndex, minusEnd);
            int nonEnd = 1;
            while(nonEnd<n) {
                push(nonEnd);
                if(minTree[2*nonEnd+1]<=target) {
                    nonEnd*=2;
                    nonEnd++;
                } else {
                    nonEnd*=2;
                }
            }
            nonEnd-=n;
            int start2 = nonEnd-count+1;
            //cout << startIndex << " " << minusEnd << " " << start2 << " " << nonEnd << endl;
            rangeAdd(start2, nonEnd);
        }
    }
    void explore(int index, int i=1) {
        if(i>=n) return;
        push(i);
        if(begin[2*i]<=index&&end[2*i]>=index) {
            explore(index, 2*i);
        } else {
            explore(index, 2*i+1);
        }
    }
    void rangeAdd(int l, int r, int i=1) {
        if(l>r) return;
        if(i>=n) {
            minTree[i]++;
            maxTree[i]++;
            return;
        }
        push(i);
        if(l==begin[i]&&r==end[i]) {
            minTree[i]++;
            maxTree[i]++;
            upd[i]++;
            return;
        }
        if(begin[2*i]<=r&&end[2*i]>=l) {
            rangeAdd(l, min(r,end[2*i]), 2*i);
        }
        if(begin[2*i+1]<=r&&end[2*i+1]>=l) {
            rangeAdd(max(l, begin[2*i]), r, 2*i+1);
        }
        minTree[i]=min(minTree[2*i], minTree[2*i+1]);
        maxTree[i]=max(maxTree[2*i], maxTree[2*i+1]);
    }
    int count(ll match, int i=1) {
        if(i<n) push(i);
        if(minTree[i]==match&&maxTree[i]==match) return end[i]-begin[i]+1;
        int c = 0;
        if(minTree[2*i]<=match&&maxTree[2*i]>=match) c+=count(match, i*2);
        if(minTree[2*i+1]<=match&&maxTree[2*i+1]>=match) c+=count(match,2*i+1);
        return c;
    }
    void print() {
        FOR(i, 1, n) {
            push(i);
        }
        cout << minTree << endl;
    }
};
int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(0);
    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);
    //debug=false; //ENABLE before submitting code to disable printArrays
    int n,m;
    cin >> n >> m;
    vector<ll> initial(n);
    SegTree st(n);
    F0R(i, n) cin >> initial[i];
    sort(begin(initial), end(initial));
    st.build(initial);
    // st.print();
    F0R(i, m) {
        char c;
        ll a,b;
        cin >> c >> a >> b;
        if(c=='F') {
            st.apply(a,b);
        } else {
            cout << st.query(a,b) << endl;
        }

        //st.print();
    }
    return 0;
}

Compilation message (stderr)

grow.cpp: In member function 'void SegTree::build(std::vector<long long int>)':
grow.cpp:6:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
      |                                        ^
grow.cpp:7:18: note: in expansion of macro 'FOR'
    7 | #define F0R(i,a) FOR(i,0,a)
      |                  ^~~
grow.cpp:75:9: note: in expansion of macro 'F0R'
   75 |         F0R(i, heights.size()) {
      |         ^~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10