Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### redgulli's blog

By redgulli, history, 4 weeks ago, , I have been trying out this problem on Hackerearth.

This is my code:

#include<bits/stdc++.h>
using namespace std;

int evencount;
bool A;
int num;
void build(int node,int start,int end)
{
if(start==end)
{
evencount[node]=(A[start]%2==0);
return;
}
int mid=start+(end-start)/2;
build(2*node+1,start,mid);
build(2*node+2,mid+1,end);
int left=2*node+1;
int right=2*node+2;
evencount[node]=evencount[left]+evencount[right];
}

void update(int node,int start,int end,int idx,int val)
{
if(start==end)
{
A[idx]=val%2;
evencount[node]=(val%2==0);
return;
}
int mid=start+(end-start)/2;
if(idx <= mid)
{
update(2*node+1,start,mid,idx,val);
}
else{
update(2*node+2,mid+1,end,idx,val);
}
int left=2*node+1;
int right=2*node+2;
evencount[node]=evencount[left]+evencount[right];
}

int query(int node,int start,int end,int left,int right)
{
if(end < left || start > right)
{
return 0;
}
if(left<=start && end>=right)
return evencount[node];

int mid=start+(end-start)/2;
int p1,p2;
p1=query(2*node+1,start,mid,left,right);
p2=query(2*node+2,mid+1,end,left,right);
return p1+p2;
}

int main(){
int N;
cin>>N;
for(int i=0;i<N;i++)
{
cin>>num;
A[i]=num%2;
}
int Q;
cin>>Q;
for(int i=0;i<Q;i++)
{
int q,a,b;
cin>>q>>a>>b;
if(q==0)
update(0,0,N,a-1,b);
else
{
int t=query(0,0,N,a-1,b-1);
if(q==1)
cout<<t<<endl;
else
cout<<(b-a+1)-t<<endl;
}
}
}


I have optimized it as much as I can. It is still giving memory limit exceeded. Where and how can I optimize this code further in terms of memory ? Comments (18)
 » Hey! Random observation based on the problem URL: Have you considered to use Fenwick / BIT tree which requires 4 times less memory?
•  » » Some facts about memory limit for this problem: Time Limit: 1,0 sec(s) for each input file. Memory Limit: 256 MB Source Limit: 1024 KB Why he exceeded 256MB with 4MB Segment Tree?
•  » » Well, I don't know about Fenwick trees. But I will give it a shot after learning Fenwick trees. Thanks.
 » You can use fenwick tree for optimizing memory.
•  » » Yes, but the question can be solved in segment tree as well, according to the question tag. But I will try Fenwick as well. Thanks.
•  » » » You can decrease memory usage by this trick: Let your current node be x. Let y = (l + r) / 2. (l and r are your node intervals) Now the left child of node x will be x + 1. And the right child will be x + ((y — l + 1) << 1). The memory usage will be 2n (or 2n — 1). If you wanna know why this works, check cp algorithms segtree section. (The ids of nodes that i explained where all 0_based.)
 » 4 weeks ago, # | ← Rev. 5 →   I added in your code 3 types of assert: assert_re(bool q), assert_tle(bool q) and assert_mle(bool q). If bool q will be false, solution will be finished with verdicts RE, TLE or MLE and you will see which assert was failed. https://pastebin.com/iAXFHf05assert_mle(depth <= 20); was failed at line 72, it means, that you have a bug and query function never ends and have infinity recursion calls without return. So, you have a bug in your logic, you should debug it and fix it.
•  » » Thanks for your help. Really appreciate it.
•  » » There are several compilation flags, which can detect problem without code change: Flags-std=c++17 -Wall -Wextra -Wshadow -Wconversion -g -fsanitize=address -fsanitize=undefined -fuse-ld=gold -D_GLIBCXX_DEBUG -O2 . Then, if you run original code on sample, you will get following exceptions: Exceptionsa.cpp:55:15: runtime error: signed integer overflow: 1207959551 * 2 cannot be represented in type 'int' AddressSanitizer:DEADLYSIGNAL ================================================================= ==5621==ERROR: AddressSanitizer: stack-overflow on address 0x7ffd465ffff8 (pc 0x000000403d87 bp 0x000000000001 sp 0x7ffd46600000 T0) #0 0x403d86 in query(int, int, int, int, int) /home/veschii/nevstrui/cf/a.cpp:55 #1 0x403d86 in query(int, int, int, int, int) /home/veschii/nevstrui/cf/a.cpp:44 #2 0x403d8b in query(int, int, int, int, int) /home/veschii/nevstrui/cf/a.cpp:55 #3 0x403d8b in query(int, int, int, int, int) /home/veschii/nevstrui/cf/a.cpp:44 #4 0x403d8b in query(int, int, int, int, int) /home/veschii/nevstrui/cf/a.cpp:55 #5 0x403d8b in query(int, int, int, int, int) /home/veschii/nevstrui/cf/a.cpp:44 #6 0x403d8b in query(int, int, int, int, int) /home/veschii/nevstrui/cf/a.cpp:55 #7 0x403d8b in query(int, int, int, int, int) /home/veschii/nevstrui/cf/a.cpp:44 #8 0x403d8b in query(int, int, int, int, int) /home/veschii/nevstrui/cf/a.cpp:55 #9 0x403d8b in query(int, int, int, int, int) /home/veschii/nevstrui/cf/a.cpp:44 #10 0x403d8b in query(int, int, int, int, int) /home/veschii/nevstrui/cf/a.cpp:55 #11 0x403d8b in query(int, int, int, int, int) /home/veschii/nevstrui/cf/a.cpp:44 #12 0x403d8b in query(int, int, int, int, int) /home/veschii/nevstrui/cf/a.cpp:55 ... ... #495 0x403d8b in query(int, int, int, int, int) /home/veschii/nevstrui/cf/a.cpp:44 #496 0x403d8b in query(int, int, int, int, int) /home/veschii/nevstrui/cf/a.cpp:55 #497 0x403d8b in query(int, int, int, int, int) /home/veschii/nevstrui/cf/a.cpp:44 SUMMARY: AddressSanitizer: stack-overflow /home/veschii/nevstrui/cf/a.cpp:55 in query(int, int, int, int, int) ==5621==ABORTING Obviously, there is an infinite recursion here.
•  » » » Awesome. Same result can be given by running in Codeforces Custom Invocation with Clang++17 Diagnostics on sample, but without stack trace.
•  » » » » Clang++17 Diagnostics on following code just write 2: UB#include using namespace std; int main() { int a = 0; int b = a++ + ++a; cout << b << endl; } Whereas mine compiler warnings me: Warningsa.cpp: In function ‘int main()’: a.cpp:7:11: warning: operation on ‘a’ may be undefined [-Wsequence-point] int b = a++ + ++a;  OoopsAnd then writes 2)
•  » » » Kind of off-topic, but why -fuse-ld=gold? Does default linker (ld in Linux) have some problem?
•  » » » » Yes: Compile without -fuse-ld=goldg++-8 -std=c++17 -Wall -Wextra -Wshadow -Wconversion -g -fsanitize=address -fsanitize=undefined -D_GLIBCXX_DEBUG -O2 -o a a.cpp /usr/bin/ld: unrecognized option '--push-state--no-as-needed' /usr/bin/ld: use the --help option for usage information collect2: error: ld returned 1 exit status Makefile:7: recipe for target 'a' failed make: *** [a] Error 1 I google it and find this. So I just add this flag to my Makefile)
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   I use a superset of your compile flags in my makefile. I never had a problem. MakefileFILE?=cprog CXXFLAGS=-Wall -Wextra -pedantic -std=c++17 -O2 -Wshadow -Wformat=2 -Wfloat-equal -Wconversion -Wlogical-op -Wshift-overflow=3 -Wduplicated-cond -Wcast-qual -Wcast-align -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC -D_FORTIFY_SOURCE=2 -fsanitize=address -fsanitize=undefined -fsanitize-recover -fstack-protector -g -Wno-variadic-macros DBG=-DLOCAL run: ${FILE} ./${FILE} ${FILE}:${FILE}.cc @${CXX}${CXXFLAGS} ${DBG} -o$@ \$< What platform are you on?Also, as per the last comment on your linked thread, it was a bug in G++7 and fixed in all distros a year back. It's weird that you still get that error.
•  » » » » » » Ubuntu 16.04 LTSgcc version 5.5.0 20171010Your flags on my computer get this eror: Errorg++-8 -Wall -Wextra -pedantic -std=c++17 -O2 -Wshadow -Wformat=2 -Wfloat-equal -Wconversion -Wlogical-op -Wshift-overflow=3 -Wduplicated-cond -Wcast-qual -Wcast-align -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC -D_FORTIFY_SOURCE=2 -fsanitize=address -fsanitize=undefined -fsanitize-recover -fstack-protector -g -Wno-variadic-macros -o a a.cpp g++-8: error: argument to ‘-Wshift-overflow=’ is not between 0 and 2 Makefile:7: recipe for target 'a' failed make: *** [a] Error 1 If I set -Wshift-overflow= to 0 or 1 or 2, then I get the same error as in the previous comment. My MakefileCC=g++-8 CFLAGS=-std=c++17 -Wall -Wextra -Wshadow -Wconversion -g -fsanitize=address -fsanitize=undefined -fuse-ld=gold -D_GLIBCXX_DEBUG -O2 all: a b c d e f g h i j k l m a: a.cpp $(CC)$(CFLAGS) -o $@$^ b: b.cpp $(CC)$(CFLAGS) -o $@$^ c: c.cpp $(CC)$(CFLAGS) -o $@$^ d: d.cpp $(CC)$(CFLAGS) -o $@$^ e: e.cpp $(CC)$(CFLAGS) -o $@$^ f: f.cpp $(CC)$(CFLAGS) -o $@$^ g: g.cpp $(CC)$(CFLAGS) -o $@$^ h: h.cpp $(CC)$(CFLAGS) -o $@$^ i: i.cpp $(CC)$(CFLAGS) -o $@$^ j: j.cpp $(CC)$(CFLAGS) -o $@$^ k: k.cpp $(CC)$(CFLAGS) -o $@$^ l: l.cpp $(CC)$(CFLAGS) -o $@$^ m: m.cpp $(CC)$(CFLAGS) -o $@$^ Offtop. MikeMirzayanov, why one dollar in editing comment changes to three dollars in comment? How can I write exactly one dollar?
•  » » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   GCC 7 (7.3.0-16ubuntu3) is still broken on Ubuntu 16.04 and earlier. — StackoverflowThis is regarding using UBsan with GCC. This leads me to believe that this bug is unfixable for you till you upgrade your Ubuntu version.Conclusion: the alternative linker is necessary for you.
 » 4 weeks ago, # | ← Rev. 3 →   Read the comments and the corresponding changes I made to your code. Do reply back if you don't understand the reasoning behind the changes, although I suggest you work them out yourself to understand where you went wrong :)I submitted the commented code and it got accepted. Also, you can look at my code for reference. Your code modified#include using namespace std; int evencount; bool A; int num; void build(int node,int start,int end) { if(start==end) { evencount[node]=(A[start]%2==0); return; } int mid=start+(end-start)/2; build(2*node+1,start,mid); build(2*node+2,mid+1,end); int left=2*node+1; int right=2*node+2; evencount[node]=evencount[left]+evencount[right]; } void update(int node,int start,int end,int idx,int val) { // You missed this condition // Don't update if the index doesn't fall in the current range if(idx < start || idx > end) return ; else if(start==end) { A[idx]=val%2; evencount[node]=(val%2==0); return; } int mid=start+(end-start)/2; if(idx <= mid) { update(2*node+1,start,mid,idx,val); } else{ update(2*node+2,mid+1,end,idx,val); } int left=2*node+1; int right=2*node+2; evencount[node]=evencount[left]+evencount[right]; } // This function of yours is messed up // This is causing TLE. Update is running fine int query(int node,int start,int end,int left,int right) { if(end < left || start > right) { return 0; } // This condition in your original code is wrong // You have to check if the query segment completely envelopes the current segment if(left<=start && right>=end) return evencount[node]; int mid=start+(end-start)/2; int p1,p2; p1=query(2*node+1,start,mid,left,right); p2=query(2*node+2,mid+1,end,left,right); return p1+p2; } int main(){ int N; cin>>N; for(int i=0;i>num; A[i]=num%2; } // You forgot to build the tree build(0, 0, N-1); int Q; cin>>Q; for(int i=0;i>q>>a>>b; if(q==0) update(0,0,N-1,a-1,b); else { int t=query(0,0,N-1,a-1,b-1); if(q==1) cout< using namespace std; //Optimizations #pragma comment(linker, "/stack:200000000") #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //save time #define endl '\n' #define db(x) cerr << "> " << #x << ": " << x << endl typedef long long ll; //for sorting #define all(a) a.begin(),a.end() //Constants #define PI 3.141592653593 #define MOD 1000000007LL #define EPS 0.000000001 #define INF 0X3f3f3f3f //loops #define REP(i,n) for(int i=0;i<(n);++i) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define DFOR(i,a,b) for(int i=(a);i>=(b);--i) //vectors #define vi vector #define vll vector #define vii vector> #define vlll vector> #define pb push_back //pairs #define pi pair #define pll pair #define mp make_pair #define F first #define S second //fast I/O #ifndef _WIN32 #define getchar getchar_unlocked #define putchar putchar_unlocked #endif #define gc getchar #define pc putchar //If using cin and cout #define IOS ios::sync_with_stdio(false) #define TIE cin.tie(NULL);cout.tie(NULL) //queue #define di deque #define dll deque #define qi queue #define PQ priority_queue //general #define E empty() //Declare all variables and methods needed between this comment and the next one(OCD lol) const int MAXN=1e5+10; const int MAXK=0; int arr[MAXN], tree[MAXN<<2]; void buildTree(int low, int high, int pos) { int mid =(low+high)>>1; if(low == high) tree[pos] = arr[mid]; else { buildTree(low, mid, 2*pos); buildTree(mid+1, high, 2*pos+1); tree[pos] = tree[2*pos] + tree[2*pos+1]; } } int queryTree(int low, int high, int pos, int qLow, int qHigh) { int mid = (low+high)>>1; if(qLow > high || qHigh < low) return 0; else if(qLow <= low && qHigh >= high) return tree[pos]; else return queryTree(low, mid, 2*pos, qLow, qHigh) + queryTree(mid+1, high, 2*pos+1, qLow, qHigh); } void updateTree(int low, int high, int pos, int idx, int val) { int mid = (low+high)>>1; if(idx < low || idx > high) return ; else if(low == high) tree[pos] = val&1; else { updateTree(low, mid, 2*pos, idx, val); updateTree(mid+1, high, 2*pos+1, idx, val); tree[pos] = tree[2*pos] + tree[2*pos+1]; } } //Main function int main() { IOS; TIE; int n; cin>>n; FOR(i, 1, n+1) cin>>arr[i], arr[i] &= 1; buildTree(1, n, 1); int q; cin>>q; while(q--) { int q, a, b; cin>>q>>a>>b; if(!q) updateTree(1, n, 1, a, b); else { int ans = queryTree(1, n, 1, a, b); if(q&1) ans = (b-a+1) - ans; cout<
•  » » Thanks man. I am really new to Segment Tree. Thanks for your help.