What’s wrong with my code : CodeChef: Practical coding for everyone
I used Fast I/O still show TLE.
I just want to ask whats wrong with my code why does it shows TLE.
https://www.codechef.com/viewsolution/50682307
There is a bug in the testing environment of this question dont try this…
It requires a more optimal solution probably or the test cases would have been generated in such a way that Fenwick tree submissions fail.
Edit: My Submission passed. I implemented the Segment tree. Here’s my Code.
CPP Code
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int tree_size = 0;
ll segment_tree_query(vector<ll>& tree, int index) {
index += tree_size;
ll sum = 0;
for(; index > 0; sum += tree[index], index >>= 1);
return sum;
}
void segment_tree_update(vector<ll>& tree, int node, int node_lb, int node_ub, int query_lb, int query_ub, int x) {
if(query_lb > node_ub || query_ub < node_lb) {
return;
}
else if(query_lb <= node_lb && node_ub <= query_ub) {
tree[node] += x;
}
else {
segment_tree_update(tree, 2 * node, node_lb, (node_lb + node_ub) / 2, query_lb, query_ub, x);
segment_tree_update(tree, 2 * node + 1, (node_lb + node_ub) / 2 + 1, node_ub, query_lb, query_ub, x);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n = 0, m = 0, c = 0;
cin >> n >> m >> c;
vector<int> arr(n, c);
while((n & (n - 1)) != 0) {
n++;
}
tree_size = n;
arr.resize(n, 0);
vector<ll> tree(2 * n, 0);
for(int i = 2 * n - 1; i >= n; i--) {
tree[i] = arr[i - n];
}
for(int q = 0; q < m; q++) {
char query;
cin >> query;
if(query == 'Q') {
int index = 0;
cin >> index;
cout << segment_tree_query(tree, index - 1) << '\n';
}
else {
int u = 0, v = 0, x = 0;
cin >> u >> v >> x;
segment_tree_update(tree, 1, tree_size, 2 * tree_size - 1, u + tree_size - 1, v + tree_size - 1, x);
}
}
return 0;
}
Python Simple Fenwick Tree (BIT):
import sys
inp=sys.stdin.readline
n,m,c=map(int,inp().split())
ft=[0]*(n+1)
def update(i,val):
while i<=n:
ft[i]+=val
i += i & -i
def query(i):
ans=0
while i>0:
ans+=ft[i]
i -= i & -i
return ans
update(1,c)
for _ in range(m):
arr=list(inp().split())
if arr[0]=="Q":
p=int(arr[1])
res=query(p)
print(res)
else:
u,v,k=int(arr[1]),int(arr[2]),int(arr[3])
update(u,k)
update(v+1,-k)