When I first got MLE, I suspected it might be because of #define int long long, but even after changing that I still got MLE. I couldn't figure out what was wrong as I was sure that the space was O(n).
When I used std::set instead of std::deque it used only 100MB memory.
std::deque code
...
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #define int long long
#define float double
#define all(x) (x).begin(), (x).end()
#define pnl cout << "\n"
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << (#x) << " " << (x) << "\n"
#else
#define dbg(x) 42
#endif
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using vi = vector<int>;
using vvi = vector<vi>;
using ii = array<int, 2>;
using vii = vector<ii>;
template <typename T>
istream &operator>>(istream &in, vector<T> &a) {
for (auto &x : a) in >> x;
return in;
}
template <typename T>
ostream &operator<<(ostream &out, vector<T> &a) {
for (auto &x : a) out << x << " ";
return out;
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int inf = numeric_limits<int>::max();
struct Node {
Node *l = 0, *r = 0;
int lo, hi, mset = inf, madd = 0, val = 0;
Node(int lo,int hi):lo(lo),hi(hi){} // Large interval of 0
Node(vector<int>& v, int lo, int hi) : lo(lo), hi(hi) {
if (lo + 1 < hi) {
int mid = lo + (hi - lo) / 2;
l = new Node(v, lo, mid); r = new Node(v, mid, hi);
val = l->val + r->val;
}
else val = v[lo];
}
int query(int L, int R) {
if (R <= lo || hi <= L) return 0;
if (L <= lo && hi <= R) return val;
push();
return l->query(L, R) + r->query(L, R);
}
void set(int L, int R, int x) {
if (R <= lo || hi <= L) return;
if (L <= lo && hi <= R) {
mset = x;
madd = 0;
val = x * (hi - lo);
}
else {
push();
l->set(L, R, x);
r->set(L, R, x);
val = l->val + r->val;
}
}
void add(int L, int R, int x) {
if (R <= lo || hi <= L) return;
if (L <= lo && hi <= R) {
if (mset != inf) mset += x;
else madd += x;
val += x * (hi - lo);
}
else {
push();
l->add(L, R, x);
r->add(L, R, x);
val = l->val + r->val;
}
}
void push() {
if (!l) {
int mid = lo + (hi - lo) / 2;
l = new Node(lo, mid); r = new Node(mid, hi);
}
if (mset != inf) {
l->set(lo, hi, mset);
r->set(lo, hi, mset);
mset = inf;
}
else if (madd) {
l->add(lo, hi, madd);
r->add(lo, hi, madd);
madd = 0;
}
}
};
void solve(int testcase) {
int n; cin >> n;
vi a(n); cin >> a;
map<int, deque<int>> pos;
for (int i = 0; i < n; i++) {
pos[a[i]].push_back(i);
}
vi op(n);
Node st(a, 0, n);
Node st2(op, 0, n);
int m; cin >> m;
while (m--) {
int clr; cin >> clr;
if (pos.find(clr) == pos.end()) continue;
auto &dq = pos[clr];
if (dq.size() < 2) continue;
while (dq.size()) {
int l = dq.front();
if (st2.query(l, l + 1)) {
dq.pop_front();
continue;
}
break;
}
while (dq.size()) {
int r = dq.back();
if (st2.query(r, r + 1)) {
dq.pop_back();
continue;
}
break;
}
if (dq.size() >= 2) {
int l = dq.front();
int r = dq.back();
st.set(l, r + 1, a[l]);
if (r > l + 1) st2.add(l + 1, r, 1);
}
}
for (int i = 0; i < n; i++) {
cout << st.query(i, i + 1) << " ";
}
pnl;
}
int32_t main() {
using namespace chrono;
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
auto start = high_resolution_clock::now();
int T = 1; // cin >> T;
for (int t = 1; t <= T; t++) {
solve(t);
}
auto end = high_resolution_clock::now();
auto duration = duration_cast<milliseconds>(end - start);
#ifndef ONLINE_JUDGE
cerr << "Time: " << duration.count() << " ms\n";
#endif
return 0;
}
std::set code
...
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #define int long long
#define float double
#define all(x) (x).begin(), (x).end()
#define pnl cout << "\n"
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << (#x) << " " << (x) << "\n"
#else
#define dbg(x) 42
#endif
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using vi = vector<int>;
using vvi = vector<vi>;
using ii = array<int, 2>;
using vii = vector<ii>;
template <typename T>
istream &operator>>(istream &in, vector<T> &a) {
for (auto &x : a) in >> x;
return in;
}
template <typename T>
ostream &operator<<(ostream &out, vector<T> &a) {
for (auto &x : a) out << x << " ";
return out;
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int inf = numeric_limits<int>::max();
struct Node {
Node *l = 0, *r = 0;
int lo, hi, mset = inf, madd = 0, val = 0;
Node(int lo,int hi):lo(lo),hi(hi){} // Large interval of 0
Node(vector<int>& v, int lo, int hi) : lo(lo), hi(hi) {
if (lo + 1 < hi) {
int mid = lo + (hi - lo) / 2;
l = new Node(v, lo, mid); r = new Node(v, mid, hi);
val = l->val + r->val;
}
else val = v[lo];
}
int query(int L, int R) {
if (R <= lo || hi <= L) return 0;
if (L <= lo && hi <= R) return val;
push();
return l->query(L, R) + r->query(L, R);
}
void set(int L, int R, int x) {
if (R <= lo || hi <= L) return;
if (L <= lo && hi <= R) {
mset = x;
madd = 0;
val = x * (hi - lo);
}
else {
push();
l->set(L, R, x);
r->set(L, R, x);
val = l->val + r->val;
}
}
void add(int L, int R, int x) {
if (R <= lo || hi <= L) return;
if (L <= lo && hi <= R) {
if (mset != inf) mset += x;
else madd += x;
val += x * (hi - lo);
}
else {
push();
l->add(L, R, x);
r->add(L, R, x);
val = l->val + r->val;
}
}
void push() {
if (!l) {
int mid = lo + (hi - lo) / 2;
l = new Node(lo, mid); r = new Node(mid, hi);
}
if (mset != inf) {
l->set(lo, hi, mset);
r->set(lo, hi, mset);
mset = inf;
}
else if (madd) {
l->add(lo, hi, madd);
r->add(lo, hi, madd);
madd = 0;
}
}
};
void solve(int testcase) {
int n; cin >> n;
vi a(n); cin >> a;
map<int, set<int>> pos;
for (int i = 0; i < n; i++) {
pos[a[i]].insert(i);
}
vi op(n);
Node st(a, 0, n);
Node st2(op, 0, n);
int m; cin >> m;
while (m--) {
int clr; cin >> clr;
if (pos.find(clr) == pos.end()) continue;
auto &dq = pos[clr];
if (dq.size() < 2) {
pos.erase(clr);
continue;
}
while (dq.size()) {
int l = *dq.begin();
if (st2.query(l, l + 1)) {
dq.erase(dq.begin());
continue;
}
break;
}
while (dq.size()) {
int r = *prev(dq.end());
if (st2.query(r, r + 1)) {
dq.erase(prev(dq.end()));
continue;
}
break;
}
if (dq.size() >= 2) {
int l = *dq.begin();
int r = *prev(dq.end());
st.set(l, r + 1, a[l]);
if (r > l + 1) st2.add(l + 1, r, 1);
} else {
pos.erase(clr);
}
}
for (int i = 0; i < n; i++) {
cout << st.query(i, i + 1) << " ";
}
pnl;
}
int32_t main() {
using namespace chrono;
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
auto start = high_resolution_clock::now();
int T = 1; // cin >> T;
for (int t = 1; t <= T; t++) {
solve(t);
}
auto end = high_resolution_clock::now();
auto duration = duration_cast<milliseconds>(end - start);
#ifndef ONLINE_JUDGE
cerr << "Time: " << duration.count() << " ms\n";
#endif
return 0;
}
Can anybody explain why std::deque has such high memory usage?
