SPREAD - Editorial

editorial
, , , ,
22

What’s wrong with my code : CodeChef: Practical coding for everyone
I used Fast I/O still show TLE.

23

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…

24

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;
}
25

Why is this AC while this this WA? :thinking:

26

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)