#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
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()) {
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1040 ms |
10328 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
604 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
660 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
143 ms |
2032 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
283 ms |
2236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1058 ms |
6032 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1056 ms |
10332 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1024 ms |
10072 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1026 ms |
10584 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1018 ms |
10540 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
447 ms |
12164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
