Sorry but it’s actually an easy problem. Involving BIT or segment tree doesn’t make it medium. The logic is very straight forward and simple. Hence it is marked as easy.
And its not marked easy because of weak test data. That was a mistake at setter or tester part.
In my code task 0 is giving WA and task 1 is giving AC. I am not understanding what is wrong in my code. Please help.
#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long int
signed main() {
int n, q;
cin >> n >> q;
vector v(n);
for (auto &p : v)
cin >> p;
while (q--) {
int fst;
cin >> fst;
if (fst == 1) {
int l, r, x;
cin >> l >> r >> x;
for (int i = l - 1; i < r; i++) {
v[i] = v[i] +
((x + i + 1 - l) * (x + i + 1 - l));
}
} if (fst == 2) {
int index;
cin >> index;
cout << v[index - 1] << endl;
}
}
}
Hi guys, sorry for the delay in complete editorial. Have added explanation.
3 Likes
Stupid mistakes again and again - maybe they’re not fit for the role.
PS: I am talking about the person who generated test cases.
oops sorry for that… i was curious to know why the brute force for my solution giving TLE didnt realize i shared a wrong link.
https://www.codechef.com/viewsolution/48321592
can anyone help with this?
why is this giving wrong answers?
cin>>l>>r>>x;
for(int i=l;i<=r;i++)
a[i]=a[i]+(x+i-l)*(x+i-l);
}
In the expression (x + i - l) * (x + i - l), all operands are Integers. Hence, the result will also be an Integer. Since this product may exceed the limits of an int, you are supposed to a use a bigger data type, in this case - long.
Thanks.
I’m using the same FenwickTree implementation as the Tester’s Solution (but changed a bit) but this gives WA. Any idea why? There are some of my custom Marcos but it should be legible.
template<typename T>
struct FenwickTree {
vector<T> data;
FenwickTree(size_t n) {
data.resize(n);
}
FenwickTree(const vector<T> &v): FenwickTree(v.size()) {
data.resize(v.size());
fo(i, 0, v.size())
inc(i, v[i]);
}
void fast_init(const vector<T> &v) {
data = v;
fo(i, 0, v.size()) {
size_t np = i | (i + 1);
if (np < v.size())
data[np] += data[i];
}
}
void add(size_t pos, T val) {
for (; pos < data.size(); pos |= pos + 1) {
data[pos] += val;
}
}
void range_add(size_t posL, size_t posR, T val) {
add(posL, val);
add(posR+1, -val);
}
T sum(size_t pos) const {
T ret = 0;
for (++pos; pos; pos &= pos - 1)
ret += data[pos - 1];
return ret;
}
};
void solve(int testcase) {
int n, q; cin >> n >> q;
vll a(n); iter(x, a) cin >> x;
FenwickTree<ll> t1(n), t2(n), t3(n);
fo(_, 0, q) {
int type; cin >> type;
if (type == 1) {
int l, r, x; cin >> l >> r >> x;
int y = x - l;
--l, --r;
t1.range_add(l, r, y*y);
t2.range_add(l, r, y*2);
t3.range_add(l, r, 1);
} else {
int y; cin >> y; --y;
cout <<
a[y]
+ t1.sum(y)
+ t2.sum(y) * (y+1)
+ t3.sum(y) * (y+1) * (y+1)
<< '\n';
}
}
}Try using long long int instead of int
1 Like
its probably because of
Later you are doing
If y=10^5 then y*y overflows int.
1 Like
Because you are assuming queries are always in pair of type 1, type 2 which is not true. There can few type 1 queries followed by all type 2 queries.
Read Editorial 
https://www.codechef.com/viewsolution/48337977
I tried using BIT can anyone please tell me where I’m going wrong.
I didn’t understand the range_add function in Editorialist’s Solution. Why are we adding val at l and subtracting val at r + 1?
same bro, pura mood kharab kar diya
can anyone tell me where i am doing it wrong it is showing SIGSEGV runtime error it is a bruteforce but still i want to know where i am doing wrong
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main() {
ll n,q;
ll l,r,x,z,y;
cin>>n>>q;
vector a(n);
for(ll i=1;i<=n;++i){
cin>>a[i];
}
for(ll i=0;i<q/2;++i){
cin>>z>>l>>r>>x;
for(ll i=l; i<=r; ++i){
a[i] += pow((x+i-l),2);
}
cin>>z>>y;
cout<<a[y]<<endl;
}
return 0;
}
So you mean all those who got higher rank because of it will still get ratings, holy moly this is so unprofessional.
On the contrary, it’s professional because they aren’t adding test data after the contest is over. All participants assumed that they won’t add test data after the contest because it wasn’t announced beforehand. Brute force solutions TLEing against the test data might not be the only consequence of addition of new data. It can affect other participants too. What if someone got RTE in contest on the new test data which was easily rectifiable had they known something was wrong? Sometimes you get lucky, sometimes you don’t.
1 Like