I am trying to solve UVa 11402 Ahoy the pirates but i can’t get what’s wrong with my lazy updating. Can someone help?
@kylethenewbie
Sorry I thinks its wrong answer 
Its quite annoying… I am not aware about that platform…
Have any link of a simple very easy problem on that platform so that can I can try getting one AC before checking this code to see how it works there ?
I tried all the test cases given in debug section and edited code works fine…
code
#include <bits/stdc++.h>
using namespace std;
struct Tree
{
vector<int> tree, arr;
vector< queue<int> > lazy;
int n;
void build(int node, int start, int end)
{
if (start == end)
tree[node] = arr[start];
else
{
int mid = (start+end)/2;
build(node*2, start, mid);
build(node*2+1, mid+1, end);
tree[node] = tree[node*2] + tree[node*2+1];
}
}
int reduce(int mode, int start, int end, int val)
{
if (mode == 1)
return end-start+1;
else if (mode == 2)
return 0;
else if (mode == 3)
return end-start+1-val;
else
return val;
}
void lazy_prog(int node, int start, int end)
{
while(lazy[node].size() != 0)
{
//cout << "Pushing node " << node << '\n';
tree[node] = reduce(lazy[node].front(), start, end, tree[node]);
if (start != end)
{
lazy[node*2].push(lazy[node].front());
lazy[node*2+1].push(lazy[node].front());
}
lazy[node].pop();
}
}
int query(int node, int start, int end, int i, int j)
{
lazy_prog(node, start, end);
if (i > end || j < start)
return 0;
if (start >= i && end <= j)
return tree[node];
int mid = (start+end)/2;
int s1 = query(node*2, start, mid, i, j);
int s2 = query(node*2+1, mid+1, end, i, j);
//cout << start << " - " << mid << ": " << s1 << " ";
//cout << mid+1 << " - " << end << ": " << s2 << '\n';
return s1 + s2;
}
void update(int node, int start, int end, int i, int j, int mode)
{
lazy_prog(node, start, end);
if (start > j || end < i)
return;
if (start >= i && end <= j)
{
tree[node] = reduce(mode, start, end, tree[node]);
if (start != end)
{
lazy[node*2].push(mode);
lazy[node*2+1].push(mode);
}
return;
}
int mid = (start+end)/2;
update(node*2, start, mid, i, j, mode);
update(node*2+1, mid+1, end, i, j, mode);
tree[node] = tree[node*2] + tree[node*2+1];
}
Tree(vector<int> a)
{
arr = a;
n = (int)a.size();
tree.resize(4*n);
lazy.resize(4*n);
build(1, 0, n-1);
}
};
int main(int argc, char** argv)
{
//ios::sync_with_stdio(0);
//cin.tie(0);
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
int t;
cin >> t;
for (int k = 0; k < t; k++)
{
string land = "";
int n;
cin >> n;
while (n--)
{
int T; cin >> T;
string s; cin >> s;
for (int i = 0; i < T; i++)
land += s;
}
vector<int> A((int)land.length());
for (int i = 0; i < (int)land.length(); i++)
A[i] = (land[i] == '1' ? 1 : 0);
Tree segtree(A);
//for (int i = 0; i < segtree.tree.size(); i++)
//cout << i << ": " << segtree.tree[i] << '\n';
cout << "Case " << k+1 << ":\n";
int q;
cin >> q;
int Q = 1;
for (int i = 0; i < q; i++)
{
char c; int a, b;
cin >> c >> a >> b;
if (c != 'S')
{
int mode;
if (c == 'F') mode = 1;
else if (c == 'E') mode = 2;
else mode = 3;
segtree.update(1, 0, A.size()-1, a, b, mode);
//cout << mode << ' ' << segtree.query(1, 0, A.size()-1, a, b) << ' ' << segtree.query(1, 0, A.size()-1, b+1, A.size()-1) << '\n';
}
else
cout << "Q" << Q++ << ": " << segtree.query(1, 0, A.size()-1, a, b) << '\n';
}
}
return 0;
}
NOT SURE
Line 44-45 as well as 84-85 seems incorrect…
As you need to handle previous value of lazy[node] before updating it again…
(Only in case of “i” type (flip) query because it uses previous value of that node and if you don’t process previous pending updates then it may cause issues)
Your edited code(seems correct logically but TLE)
#include <bits/stdc++.h>
using namespace std;
struct Tree
{
vector<int> tree, arr;
vector< queue<int> > lazy;
int n;
void build(int node, int start, int end)
{
if (start == end)
tree[node] = arr[start];
else
{
int mid = (start+end)/2;
build(node*2, start, mid);
build(node*2+1, mid+1, end);
tree[node] = tree[node*2] + tree[node*2+1];
}
}
int reduce(queue<int> mode, int start, int end, int val)
{
while(mode.size()){
if (mode.front() == 1)
val=end-start+1;
else if (mode.front() == 2)
val=0;
else if (mode.front() == 3)
val=end-start+1-val;
mode.pop();
}
return val;
}
int reduce(int mode, int start, int end, int val)
{
if (mode == 1)
return end-start+1;
else if (mode == 2)
return 0;
else if (mode == 3)
return end-start+1-val;
else
return val;
}
void lazy_prog(int node, int start, int end)
{
if (lazy[node].size() != 0)
{
//cout << "Pushing node " << node << '\n';
tree[node] = reduce(lazy[node], start, end, tree[node]);
if (start != end)
{
while(lazy[node].size()){
lazy[node*2].push(lazy[node].front());
lazy[node*2+1].push(lazy[node].front());
lazy[node].pop();
}
}
}
}
int query(int node, int start, int end, int i, int j)
{
lazy_prog(node, start, end);
if (i > end || j < start)
return 0;
if (start >= i && end <= j)
return tree[node];
int mid = (start+end)/2;
int s1 = query(node*2, start, mid, i, j);
int s2 = query(node*2+1, mid+1, end, i, j);
//cout << start << " - " << mid << ": " << s1 << " ";
//cout << mid+1 << " - " << end << ": " << s2 << '\n';
return s1 + s2;
}
void update(int node, int start, int end, int i, int j, int mode)
{
lazy_prog(node, start, end);
if (start > j || end < i)
return;
int mid = (start+end)/2;
if (start >= i && end <= j)
{
tree[node] = reduce(mode, start, end, tree[node]);
if (start != end)
{
lazy[node*2].push(mode);
lazy[node*2+1].push(mode);
}
return;
}
update(node*2, start, mid, i, j, mode);
update(node*2+1, mid+1, end, i, j, mode);
tree[node] = tree[node*2] + tree[node*2+1];
}
Tree(vector<int> a)
{
arr = a;
n = (int)a.size();
tree.resize(4*n+1);
lazy.resize(4*n+1);
build(1, 0, n-1);
}
};
int main(int argc, char** argv)
{
ios::sync_with_stdio(0);
cin.tie(0);
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
int t;
cin >> t;
for (int k = 0; k < t; k++)
{
string land = "";
int n;
cin >> n;
while (n--)
{
int T; cin >> T;
string s; cin >> s;
for (int i = 0; i < T; i++)
land += s;
}
vector<int> A((int)land.length());
for (int i = 0; i < (int)land.length(); i++)
A[i] = (land[i] == '1' ? 1 : 0);
Tree segtree(A);
//for (int i = 0; i < segtree.tree.size(); i++)
//cout << i << ": " << segtree.tree[i] << '\n';
cout << "Case " << k+1 << ":\n";
int q;
cin >> q;
int Q = 1;
for (int i = 0; i < q; i++)
{
char c; int a, b;
cin >> c >> a >> b;
if (c != 'S')
{
int mode;
if (c == 'F') mode = 1;
else if (c == 'E') mode = 2;
else mode = 3;
segtree.update(1, 0, A.size()-1, a, b, mode);
//cout << mode << ' ' << segtree.query(1, 0, A.size()-1, a, b) << ' ' << segtree.query(1, 0, A.size()-1, b+1, A.size()-1) << '\n';
}
else
cout << "Q" << Q++ << ": " << segtree.query(1, 0, A.size()-1, a, b) << '\n';
}
}
return 0;
}
Actually you may not need queue and also you don’t need to process each and every previous queries ( think which query needs to be taken care of)
Hence try to optimize the code (or maybe remove an infinite loop if any)
I can do that for you but I would prefer you to try it first…
Ping me if you can’t figure it out still…
1 Like