#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdint>
#include <cstddef>
#include <cmath>
#include <cstring>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <utility>
#include <functional>
#include <chrono>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
//#pragma GCC optimize ("Ofast")
//#pragma GCC target ("avx2")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
// data types
typedef int_fast8_t int8;
typedef int_fast16_t int16;
typedef int_fast32_t int32;
typedef int_fast64_t int64;
typedef int_fast64_t ll;
typedef uint_fast8_t uint8;
typedef uint_fast16_t uint16;
typedef uint_fast32_t uint32;
typedef uint_fast16_t uint64;
typedef uint_fast16_t ull;
typedef ptrdiff_t ptrdif;
typedef size_t uintn;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
template<typename T>
using Iterator = typename T::iterator;
template<class K, class V>
using ordered_map = tree<K, V, less<K>, rb_tree_tag, tree_order_statistics_node_update>;
template<class K>
using ordered_set = ordered_map<K, null_type>;
// constants
const int inf = 2000000011;
const ll llinf = 999999999999999989;
const int MOD = 1e9 + 7;
const double PI = acos(-1);
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, 1, 0, -1};
// macros
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define EB emplace_back
#define EF emplace_front
#define MP make_pair
#define FF first
#define SS second
// hash
namespace hash0 {
struct chash {
const uint64_t C = ll(2e18*PI)+71;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
inline ll operator()(ll x) const { return __builtin_bswap64((x ^ RANDOM) * C); }
inline ll operator()(pii p) const { return __builtin_bswap64((p.FF ^ RANDOM) * C) + p.SS; }
};
template<class K, class V>
using fast_map = gp_hash_table<K, V, chash>;
template<class K>
using fast_set = fast_map<K, null_type>;
}
using namespace hash0;
// functions
namespace functions {
inline void stop() { assert(0); }
template<typename T>
inline void sort(T& c) { sort(c.begin(), c.end()); }
template<typename T, typename S>
inline void sort(T& c, S s) { sort(c.begin(), c.end(), s); }
template<typename T>
inline void reverse(T& c) { reverse(c.begin(), c.end()); }
// lambda template: [](const C& a, const C& b) { return a > b; }
inline ll ceil0(ll a, ll b) {
return a / b + ((a ^ b) > 0 && a % b);
}
inline ll floor0(ll a, ll b) {
return a / b - ((a ^ b) < 0 && a % b);
}
ll pow0(ll a, ll b) {
ll res = 1;
for (a %= MOD; b; b >>= 1) {
if(b & 1) res = res * a % MOD;
a = a * a % MOD;
}
return res;
}
template<typename T>
string binary(T b) {
string res = "";
for (int i = sizeof(T) * 8 - 1; i >= 0; i--)
res += (b & (1 << i) ? '1' : '0');
return res;
}
template<typename T>
string binary(T b, int k) {
string res = "";
for (int i = k; i >= 0; i--)
res += ((b & (1 << i)) ? '1' : '0');
return res;
}
}
using namespace functions;
// operators
namespace operators {
namespace pairs {
template<typename T1, typename T2>
pair<T1, T2> operator+(const pair<T1, T2>& a, const pair<T1, T2>& b) { return MP(a.FF + b.FF, a.SS + b.SS); }
template<typename T1, typename T2>
pair<T1, T2> operator-(const pair<T1, T2>& a, const pair<T1, T2>& b) { return MP(a.FF - b.FF, a.SS - b.SS); }
template<typename T1, typename T2>
pair<T1, T2> operator*(const pair<T1, T2>& a, const pair<T1, T2>& b) { return MP(a.FF * b.FF, a.SS * b.SS); }
template<typename T1, typename T2>
pair<T1, T2> operator/(const pair<T1, T2>& a, const pair<T1, T2>& b) { return MP(a.FF / b.FF, a.SS / b.SS); }
template<typename T1, typename T2>
pair<T1, T2> operator%(const pair<T1, T2>& a, const pair<T1, T2>& b) { return MP(a.FF % b.FF, a.SS % b.SS); }
template<typename T1, typename T2>
pair<T1, T2> operator&(const pair<T1, T2>& a, const pair<T1, T2>& b) { return MP(a.FF & b.FF, a.SS & b.SS); }
template<typename T1, typename T2>
pair<T1, T2> operator|(const pair<T1, T2>& a, const pair<T1, T2>& b) { return MP(a.FF | b.FF, a.SS | b.SS); }
template<typename T1, typename T2>
pair<T1, T2> operator^(const pair<T1, T2>& a, const pair<T1, T2>& b) { return MP(a.FF ^ b.FF, a.SS ^ b.SS); }
template<typename T1, typename T2>
pair<T1, T2> operator-(const pair<T1, T2>& a) { return MP(-a.FF, -a.SS); }
template<typename T1, typename T2>
pair<T1, T2> operator~(const pair<T1, T2>& a) { return MP(~a.FF, ~a.SS); }
}
using namespace pairs;
namespace vectors {
namespace vector_scalar {
template<typename T>
vector<T> operator+(const vector<T>& v, const T& c) {
vector<T> v0(v.begin(), v.end());
for (auto& x : v0)
x += c;
return v0;
}
template<typename T>
vector<T> operator-(const vector<T>& v, const T& c) {
vector<T> v0(v.begin(), v.end());
for (auto& x : v0)
x -= c;
return v0;
}
template<typename T>
vector<T> operator*(const vector<T>& v, const T& c) {
vector<T> v0(v.begin(), v.end());
for (auto& x : v0)
x *= c;
return v0;
}
template<typename T>
vector<T> operator/(const vector<T>& v, const T& c) {
vector<T> v0(v.begin(), v.end());
for (auto& x : v0)
x /= c;
return v0;
}
template<typename T>
vector<T> operator%(const vector<T>& v, const T& c) {
vector<T> v0(v.begin(), v.end());
for (auto& x : v0)
x %= c;
return v0;
}
template<typename T>
vector<T> operator&(const vector<T>& v, const T& c) {
vector<T> v0(v.begin(), v.end());
for (auto& x : v0)
x &= c;
return v0;
}
template<typename T>
vector<T> operator|(const vector<T>& v, const T& c) {
vector<T> v0(v.begin(), v.end());
for (auto& x : v0)
x |= c;
return v0;
}
template<typename T>
vector<T> operator^(const vector<T>& v, const T& c) {
vector<T> v0(v.begin(), v.end());
for (auto& x : v0)
x ^= c;
return v0;
}
template<typename T>
vector<T> operator-(const vector<T>& v) {
vector<T> v0(v.begin(), v.end());
for (auto& x : v0)
x = -x;
return v0;
}
template<typename T>
vector<T> operator~(const vector<T>& v) {
vector<T> v0(v.begin(), v.end());
for (auto& x : v0)
x = ~x;
return v0;
}
}
using namespace vector_scalar;
namespace vector_vector {
template<typename T>
vector<T> operator+(const vector<T>& v0, const vector<T>& v1) {
assert(v0.size() == v1.size());
vector<T> v (v0.size());
for (int i = 0; i < v.size(); i++)
v[i] = v0[i] + v1[i];
return v;
}
template<typename T>
vector<T> operator-(const vector<T>& v0, const vector<T>& v1) {
assert(v0.size() == v1.size());
vector<T> v (v0.size());
for (int i = 0; i < v.size(); i++)
v[i] = v0[i] - v1[i];
return v;
}
template<typename T>
vector<T> operator*(const vector<T>& v0, const vector<T>& v1) {
assert(v0.size() == v1.size());
vector<T> v (v0.size());
for (int i = 0; i < v.size(); i++)
v[i] = v0[i] * v1[i];
return v;
}
template<typename T>
vector<T> operator/(const vector<T>& v0, const vector<T>& v1) {
assert(v0.size() == v1.size());
vector<T> v (v0.size());
for (int i = 0; i < v.size(); i++)
v[i] = v0[i] / v1[i];
return v;
}
template<typename T>
vector<T> operator%(const vector<T>& v0, const vector<T>& v1) {
assert(v0.size() == v1.size());
vector<T> v (v0.size());
for (int i = 0; i < v.size(); i++)
v[i] = v0[i] % v1[i];
return v;
}
template<typename T>
vector<T> operator&(const vector<T>& v0, const vector<T>& v1) {
assert(v0.size() == v1.size());
vector<T> v (v0.size());
for (int i = 0; i < v.size(); i++)
v[i] = v0[i] & v1[i];
return v;
}
template<typename T>
vector<T> operator|(const vector<T>& v0, const vector<T>& v1) {
assert(v0.size() == v1.size());
vector<T> v (v0.size());
for (int i = 0; i < v.size(); i++)
v[i] = v0[i] | v1[i];
return v;
}
template<typename T>
vector<T> operator^(const vector<T>& v0, const vector<T>& v1) {
assert(v0.size() == v1.size());
vector<T> v (v0.size());
for (int i = 0; i < v.size(); i++)
v[i] = v0[i] ^ v1[i];
return v;
}
}
using namespace vector_vector;
}
using namespace vectors;
}
using namespace operators;
// input
namespace input {
void filein(const string FILENAME) { freopen(FILENAME.c_str(), "r", stdin); }
template<typename T1, typename T2>
inline istream& operator>>(istream& is, pair<T1, T2>& p) {
return is >> p.FF >> p.SS;
}
template<typename T>
inline istream& operator>>(istream& is, vector<T>& v) {
for (auto& x : v)
is >> x;
return is;
}
inline void read() {}
template<typename T, typename... U>
inline void read(T& F, U&... S) {
cin >> F;
read(S...);
}
template<typename T>
void read(T* a, int n) {
for (int i = 0; i < n; i++)
cin >> a[i];
}
template<typename T>
void read(T* a, int l, int r) {
for (int i = l; i <= r; i++)
cin >> a[i];
}
template<typename T>
void read(vector<T>& v, int n) {
assert(n < v.size());
for (int i = 0; i < n; i++)
cin >> v[i];
}
template<typename T>
void read(vector<T>& v, int l, int r) {
assert(0 <= l && l <= r && r < v.size());
for (int i = l; i <= r; i++)
cin >> v[i];
}
}
using namespace input;
// output
namespace output {
void fileout(const string FILENAME) { freopen(FILENAME.c_str(), "w", stdout); }
void fileerr(const string FILENAME) { freopen(FILENAME.c_str(), "w", stderr); }
template<typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
return os << '(' << p.FF << ", " << p.SS << ')';
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
os << '[';
if (v.size()) {
os << *v.begin();
for (auto i = ++v.begin(); i != v.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T>
ostream& operator<<(ostream& os, const ordered_set<T>& s) {
os << '[';
if (s.size()) {
os << *s.begin();
for (auto i = ++s.begin(); i != s.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T>
ostream& operator<<(ostream& os, const fast_set<T>& s) {
os << '[';
if (s.size()) {
os << *s.begin();
for (auto i = ++s.begin(); i != s.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T>
ostream& operator<<(ostream& os, const multiset<T>& s) {
os << '[';
if (s.size()) {
os << *s.begin();
for (auto i = ++s.begin(); i != s.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T1, typename T2>
ostream& operator<<(ostream& os, const ordered_map<T1, T2>& s) {
os << '[';
if (s.size()) {
os << *s.begin();
for (auto i = ++s.begin(); i != s.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T1, typename T2>
ostream& operator<<(ostream& os, const fast_map<T1, T2>& s) {
os << '[';
if (s.size()) {
os << *s.begin();
for (auto i = ++s.begin(); i != s.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
#define debug(s, x) cerr << __FUNCTION__ << ": " << __LINE__ << ": " << s << " = " << x << '\n';
#define debug0(x) debug("val", x);
#define fixfloat(d) fixed << setprecision(d)
void print() {}
template<typename T, typename... U>
void print(T F, U... S) {
cout << F;
print(S...);
}
void printl() {}
template<typename T, typename... U>
void printl(T F, U... S) {
cout << F << '\n';
printl(S...);
}
template<typename T>
void prints(T F) {
cout << F;
}
template<typename T, typename... U>
void prints(T F, U... S) {
cout << F << ' ';
prints(S...);
}
void printc(string c) {}
template<typename T, typename... U>
void printc(const string c, T F, U... S) {
cout << F << c;
printc(c, S...);
}
template<typename T>
void printa(T* a, int n, string s = " ", string e = "\n") {
for (int i = 0; i < n; i++)
cout << a[i] << s;
cout << e;
}
template<typename T>
void printa(T* a, int l, int r, string s = " ", string e = "\n") {
for (int i = l; i < r; i++)
cout << a[i] << s;
cout << e;
}
template<typename T>
void printa(vector<T>& v, string s = " ", string e = "\n") {
for (auto x : v)
cout << x << s;
}
template<typename T>
void printa(vector<T>& v, int l, int r, string s = " ", string e = "\n") {
assert(0 <= l && l <= r && r < v.size());
for (int i = l; i <= r; i++)
cout << v[i] << s;
cout << e;
}
template<typename T>
void printa(ordered_set<T>& v, string s = " ", string e = "\n") {
for (auto x : v)
cout << x << s;
}
template<typename T>
void printa(ordered_set<T>& v, int l, int r, string s = " ", string e = "\n") {
assert(0 <= l && l <= r && r < v.size());
auto L = v.find_by_order(l), R = ++v.find_by_order(r);
for (; L != R; L++)
cout << *L << s;
cout << e;
}
template<typename T>
void printa(fast_set<T>& v, string s = " ", string e = "\n") {
for (auto x : v)
cout << x << s;
}
}
using namespace output;
// code
int N, Q, A[100005], L[400005];
pii T[400005];
inline pii merge(pii a, pii b) {
return MP(min(a.FF, b.FF), max(a.SS, b.SS));
}
void pushdown(int t, int tl, int tr) {
if (L[t]) {
T[t << 1] = MP(T[t << 1].FF + L[t], T[t << 1].SS + L[t]);
L[t << 1] += L[t];
T[t << 1 | 1] = MP(T[t << 1 | 1].FF + L[t], T[t << 1 | 1].SS + L[t]);
L[t << 1 | 1] += L[t];
L[t] = 0;
}
}
void init(int* a, int t = 1, int tl = 1, int tr = N) {
if (tl == tr) {
T[t] = MP(a[tl], a[tl]);
return;
}
int tm = (tl + tr) >> 1;
init(a, t << 1, tl, tm);
init(a, t << 1 | 1, tm + 1, tr);
T[t] = merge(T[t << 1], T[t << 1 | 1]);
}
void update(int l, int r, int v, int t = 1, int tl = 1, int tr = N) {
if (r < tl || tr < l || tr < tl)
return;
if (l <= tl && tr <= r) {
T[t] = MP(T[t].FF + v, T[t].SS + v);
L[t] += v;
return;
}
if (tl != tr)
pushdown(t, tl, tr);
int tm = (tl + tr) >> 1;
update(l, r, v, t << 1, tl, tm);
update(l, r, v, t << 1 | 1, tm + 1, tr);
T[t] = merge(T[t << 1], T[t << 1 | 1]);
}
// returns the element at index u
int query(int u, int t = 1, int tl = 1, int tr = N) {
if (tl == tr)
return T[t].FF;
else
pushdown(t, tl, tr);
int tm = (tl + tr) >> 1;
if (u <= tm)
return query(u, t << 1, tl, tm);
else
return query(u, t << 1 | 1, tm + 1, tr);
}
// returns the first index with value greater than or equal to v
int query0(int v, int t = 1, int tl = 1, int tr = N) {
if (tl == tr)
return tl;
else
pushdown(t, tl, tr);
int tm = (tl + tr) >> 1;
if (T[t << 1].SS >= v)
return query0(v, t << 1, tl, tm);
if (T[t << 1 | 1].SS >= v)
return query0(v, t << 1 | 1, tm + 1, tr);
return N + 1;
}
// returns last index with value less than or equal to v
int query1(int v, int t = 1, int tl = 1, int tr = N) {
if (tl == tr)
return tl;
else
pushdown(t, tl, tr);
int tm = (tl + tr) >> 1;
if (T[t << 1 | 1].FF <= v)
return query1(v, t << 1 | 1, tm + 1, tr);
if (T[t << 1].FF <= v)
return query1(v, t << 1, tl, tm);
return 0;
}
int main(void) {
ios_base::sync_with_stdio(0); cin.tie(0);
read(N, Q);
read(A, 1, N);
sort(A + 1, A + 1 + N);
init(A);
while (Q--) {
char t; read(t);
if (t == 'F') {
int c, h; read(c, h);
int ul = query0(h), ur = min(ul + c - 1, N); // endpoints of update
if (ur == N) {
update(ul, ur, 1);
continue;
}
int e = query(ur); // value of last elems in range
int el = query0(e), er = query1(e); // endpoints of equal range
//prints(ul, ur, e, el, er, '\n');
update(ul, el - 1, 1);
update(er - (ur - el + 1) + 1, er, 1);
}
else if (t == 'C') {
int l, r; read(l, r);
printl(query1(r) - query0(l) + 1);
}
/*
else if (t == '0') {
int u; read(u);
printl(query0(u));
}
else if (t == '1') {
int u; read(u);
printl(query1(u));
}
else if (t == '2') {
int u; read(u);
printl(query(u));
}
else if (t == '3') {
int l, r, v; read(l, r, v);
update(l, r, v);
}
*/
}
}
Compilation message
grow.cpp: In function 'void input::filein(std::string)':
grow.cpp:362:49: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
362 | void filein(const string FILENAME) { freopen(FILENAME.c_str(), "r", stdin); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
grow.cpp: In function 'void output::fileout(std::string)':
grow.cpp:415:50: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
415 | void fileout(const string FILENAME) { freopen(FILENAME.c_str(), "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
grow.cpp: In function 'void output::fileerr(std::string)':
grow.cpp:416:50: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
416 | void fileerr(const string FILENAME) { freopen(FILENAME.c_str(), "w", stderr); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
87 ms |
5060 KB |
Output is correct |
| 2 |
Correct |
131 ms |
5400 KB |
Output is correct |
| 3 |
Correct |
47 ms |
5380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
332 KB |
Output is correct |
| 2 |
Correct |
2 ms |
332 KB |
Output is correct |
| 3 |
Correct |
3 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
344 KB |
Output is correct |
| 5 |
Correct |
50 ms |
1560 KB |
Output is correct |
| 6 |
Correct |
57 ms |
1772 KB |
Output is correct |
| 7 |
Correct |
5 ms |
588 KB |
Output is correct |
| 8 |
Correct |
28 ms |
1220 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
1780 KB |
Output is correct |
| 2 |
Correct |
58 ms |
1900 KB |
Output is correct |
| 3 |
Correct |
2 ms |
460 KB |
Output is correct |
| 4 |
Correct |
35 ms |
1480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
2048 KB |
Output is correct |
| 2 |
Correct |
63 ms |
1868 KB |
Output is correct |
| 3 |
Correct |
11 ms |
676 KB |
Output is correct |
| 4 |
Correct |
56 ms |
2156 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
88 ms |
3268 KB |
Output is correct |
| 2 |
Correct |
127 ms |
5172 KB |
Output is correct |
| 3 |
Correct |
19 ms |
1492 KB |
Output is correct |
| 4 |
Correct |
39 ms |
5060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
4824 KB |
Output is correct |
| 2 |
Correct |
118 ms |
5144 KB |
Output is correct |
| 3 |
Correct |
47 ms |
5320 KB |
Output is correct |
| 4 |
Correct |
16 ms |
1540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
85 ms |
4820 KB |
Output is correct |
| 2 |
Correct |
90 ms |
5024 KB |
Output is correct |
| 3 |
Correct |
58 ms |
5308 KB |
Output is correct |
| 4 |
Correct |
15 ms |
1520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
128 ms |
5468 KB |
Output is correct |
| 2 |
Correct |
123 ms |
4940 KB |
Output is correct |
| 3 |
Correct |
32 ms |
4484 KB |
Output is correct |
| 4 |
Correct |
69 ms |
4932 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
127 ms |
5188 KB |
Output is correct |
| 2 |
Correct |
137 ms |
5524 KB |
Output is correct |
| 3 |
Correct |
189 ms |
5656 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
87 ms |
6072 KB |
Output is correct |
