[problem:101911E]↵
↵
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.↵
↵
↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
Can anybody explain why `std::deque` has such high memory usage?
↵
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.↵
↵
↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary="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;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
Can anybody explain why `std::deque` has such high memory usage?
