Hi all,↵
I am trying to code up a solution to the "[Seating](http://www.usaco.org/index.php?page=viewproblem2&cpid=231)" problem in USACO January 2013 Gold, which uses a segment tree with lazy propagation. My code passes the first 2 test cases, but fails the rest. I have checked multiple times about my code but I don't see the problem.↵
↵
~~~~~↵
#include<iostream>↵
#include<fstream>↵
#include<algorithm>↵
#include<assert.h>↵
#include<string>↵
#include<vector>↵
using namespace std;↵
int n, m;↵
int t;↵
vector<int> A;↵
vector<int> l0, r0, lazy0, lazy1,ans;↵
↵
void build(int a,int l,int r) {↵
if (r - l < 1) {↵
l0[a] = 1;↵
r0[a] = 1;↵
ans[a] = 1;↵
return;↵
}↵
l0[a] = r - l + 1;↵
r0[a] = r - l + 1;↵
ans[a] = r - l + 1;↵
build(a * 2, l, (r + l) / 2);↵
build(a * 2 + 1, (r + l) / 2 + 1, r);↵
}↵
void lazyupdate(int a,int l,int r) {↵
assert(!(lazy0[a]==1&& lazy1[a]));↵
if (lazy0[a]) {↵
lazy0[a] = 0;↵
l0[a] =ans[a]= r - l + 1;↵
r0[a] = r - l + 1;↵
if (l != r) { lazy0[2 * a] = 1; lazy0[2 * a + 1] = 1; lazy1[2 * a] = 0; lazy1[2 * a + 1] = 0; }↵
}↵
else if (lazy1[a]) {↵
l0[a] = ans[a]=r0[a] = 0;↵
if (l != r) { lazy1[2 * a] = 1; lazy1[2 * a + 1] = 1; lazy0[2 * a] = 0; lazy0[2 * a + 1] = 0; }↵
lazy1[a] = 0;↵
}↵
}↵
void updateint(int a, int l, int r) {↵
int left = 2 * a, right = 2 * a + 1;↵
l0[a] = ans[a] = r0[a] = 0;↵
if (l0[left] == ((l + r) / 2 - l + 1)) {↵
l0[a] = max(l0[a], max(l0[left], l0[left] + l0[right]));↵
}↵
else l0[a] = max(l0[a], l0[left]);↵
if (r0[right] == (r - (l + r) / 2)) {↵
r0[a] = max(r0[a], r0[right] + r0[left]);↵
}↵
else r0[a] = max(l0[a], r0[right]);↵
ans[a] = max(r0[a], max(l0[a], r0[left] + l0[right]));↵
}↵
void update0(int i, int j,int a=1, int l=0, int r=n-1) {↵
lazyupdate(a, l, r);↵
if (j<l || i>r)return;↵
↵
if (l >= i&&r <= j) {↵
l0[a] = r - l + 1;↵
r0[a] =ans[a]= r - l + 1;↵
if (l == r)return;↵
lazy0[2 * a] = 1; lazy0[2 * a + 1] = 1;↵
lazy1[2 * a] = 0; lazy1[2 * a + 1] = 0;↵
return;↵
}↵
int left = 2 * a, right = 2 * a + 1;↵
update0(i, j, left, l, (l + r) / 2);↵
update0(i, j, right, (l + r) / 2 + 1, r);↵
updateint(a, l, r);↵
↵
}↵
void update1(int i, int j, int a = 1, int l = 0, int r = n - 1) {↵
lazyupdate(a, l, r);↵
if (j<l || i>r)return;↵
↵
if (l >= i&&r <= j) {↵
l0[a] = 0;↵
r0[a] = 0;↵
ans[a] = 0;↵
if (l == r)return;↵
lazy1[2 * a] = 1; lazy1[2 * a + 1] = 1; ↵
lazy0[2 * a] = 0; lazy0[2 * a + 1] = 0;↵
return;↵
}↵
int left = 2 * a, right = 2 * a + 1;↵
update1(i, j, left, l, (l + r) / 2);↵
update1(i, j, right, (l + r) / 2 + 1, r);↵
updateint(a, l, r);↵
}↵
pair<int,int> getint(int num, int a = 1, int l = 0, int r = n - 1) {↵
lazyupdate(a, l, r);↵
if(l!=r)lazyupdate(2 * a, l, (l + r) / 2);↵
if(l!=r)lazyupdate(2 * a + 1, (l + r) / 2 + 1, r);↵
if (ans[a] == num&&r-l+1==num) {↵
return pair<int, int>(l, r);↵
}↵
int left = 2 * a, right = 2 * a + 1;↵
if (ans[left] >= num) {↵
return getint(num, a * 2, l, (l + r) / 2);↵
}↵
↵
if (r0[left] + l0[right] >= num&&r0[left]!=0) {↵
int need = num - r0[left];↵
pair<int, int> p1;↵
p1.first = (l + r) / 2 - r0[left] + 1;↵
p1.second = (l + r) / 2 + need;↵
↵
return p1;↵
}↵
if (ans[right]>=num) {↵
return getint(num, a * 2 + 1, (l + r) / 2 + 1, r);↵
}↵
assert(0);↵
}↵
int main() {↵
ifstream fin("seating.in");↵
ofstream fout("seating.out");↵
fin >> n >> m;↵
l0, r0, lazy0, lazy1, ans;↵
A.resize(n);↵
l0.resize(4 * n); r0.resize(4 * n); lazy0.resize(4 * n); lazy1.resize(4 * n); ans.resize(4 * n);↵
build(1, 0, n - 1);↵
int res = 0;↵
for (int i = 0; i < m; i++) {↵
↵
string stat;↵
fin >> stat;↵
if (stat[0] == 'A') {↵
int add; fin >> add;↵
if (ans[1] < add) {↵
res++;↵
continue;↵
}↵
pair<int, int> p = getint(add);↵
update1(p.first, p.second);↵
}↵
else {↵
int from, to; fin >> from >> to;↵
from--; to--;↵
update0(from, to);↵
}↵
}↵
fout << res << endl;↵
return 0;↵
}↵
~~~~~↵
In my segment tree, `update0` updates a given range of values to 0,` update1` updates a given range of values to 1, `updateint` updates the interval whenever some of its values have changed.`getInt(add)` gets the lowest position to insert the group of people. `lazy0` and` lazy1` stores respectively the lazy propagation for setting to 0 and setting to 1. Thank you so much for your help.↵
I am trying to code up a solution to the "[Seating](http://www.usaco.org/index.php?page=viewproblem2&cpid=231)" problem in USACO January 2013 Gold, which uses a segment tree with lazy propagation. My code passes the first 2 test cases, but fails the rest. I have checked multiple times about my code but I don't see the problem.↵
↵
~~~~~↵
#include<iostream>↵
#include<fstream>↵
#include<algorithm>↵
#include<assert.h>↵
#include<string>↵
#include<vector>↵
using namespace std;↵
int n, m;↵
int t;↵
vector<int> A;↵
vector<int> l0, r0, lazy0, lazy1,ans;↵
↵
void build(int a,int l,int r) {↵
if (r - l < 1) {↵
l0[a] = 1;↵
r0[a] = 1;↵
ans[a] = 1;↵
return;↵
}↵
l0[a] = r - l + 1;↵
r0[a] = r - l + 1;↵
ans[a] = r - l + 1;↵
build(a * 2, l, (r + l) / 2);↵
build(a * 2 + 1, (r + l) / 2 + 1, r);↵
}↵
void lazyupdate(int a,int l,int r) {↵
assert(!(lazy0[a]==1&& lazy1[a]));↵
if (lazy0[a]) {↵
lazy0[a] = 0;↵
l0[a] =ans[a]= r - l + 1;↵
r0[a] = r - l + 1;↵
if (l != r) { lazy0[2 * a] = 1; lazy0[2 * a + 1] = 1; lazy1[2 * a] = 0; lazy1[2 * a + 1] = 0; }↵
}↵
else if (lazy1[a]) {↵
l0[a] = ans[a]=r0[a] = 0;↵
if (l != r) { lazy1[2 * a] = 1; lazy1[2 * a + 1] = 1; lazy0[2 * a] = 0; lazy0[2 * a + 1] = 0; }↵
lazy1[a] = 0;↵
}↵
}↵
void updateint(int a, int l, int r) {↵
int left = 2 * a, right = 2 * a + 1;↵
l0[a] = ans[a] = r0[a] = 0;↵
if (l0[left] == ((l + r) / 2 - l + 1)) {↵
l0[a] = max(l0[a], max(l0[left], l0[left] + l0[right]));↵
}↵
else l0[a] = max(l0[a], l0[left]);↵
if (r0[right] == (r - (l + r) / 2)) {↵
r0[a] = max(r0[a], r0[right] + r0[left]);↵
}↵
else r0[a] = max(l0[a], r0[right]);↵
ans[a] = max(r0[a], max(l0[a], r0[left] + l0[right]));↵
}↵
void update0(int i, int j,int a=1, int l=0, int r=n-1) {↵
lazyupdate(a, l, r);↵
if (j<l || i>r)return;↵
↵
if (l >= i&&r <= j) {↵
l0[a] = r - l + 1;↵
r0[a] =ans[a]= r - l + 1;↵
if (l == r)return;↵
lazy0[2 * a] = 1; lazy0[2 * a + 1] = 1;↵
lazy1[2 * a] = 0; lazy1[2 * a + 1] = 0;↵
return;↵
}↵
int left = 2 * a, right = 2 * a + 1;↵
update0(i, j, left, l, (l + r) / 2);↵
update0(i, j, right, (l + r) / 2 + 1, r);↵
updateint(a, l, r);↵
↵
}↵
void update1(int i, int j, int a = 1, int l = 0, int r = n - 1) {↵
lazyupdate(a, l, r);↵
if (j<l || i>r)return;↵
↵
if (l >= i&&r <= j) {↵
l0[a] = 0;↵
r0[a] = 0;↵
ans[a] = 0;↵
if (l == r)return;↵
lazy1[2 * a] = 1; lazy1[2 * a + 1] = 1; ↵
lazy0[2 * a] = 0; lazy0[2 * a + 1] = 0;↵
return;↵
}↵
int left = 2 * a, right = 2 * a + 1;↵
update1(i, j, left, l, (l + r) / 2);↵
update1(i, j, right, (l + r) / 2 + 1, r);↵
updateint(a, l, r);↵
}↵
pair<int,int> getint(int num, int a = 1, int l = 0, int r = n - 1) {↵
lazyupdate(a, l, r);↵
if(l!=r)lazyupdate(2 * a, l, (l + r) / 2);↵
if(l!=r)lazyupdate(2 * a + 1, (l + r) / 2 + 1, r);↵
if (ans[a] == num&&r-l+1==num) {↵
return pair<int, int>(l, r);↵
}↵
int left = 2 * a, right = 2 * a + 1;↵
if (ans[left] >= num) {↵
return getint(num, a * 2, l, (l + r) / 2);↵
}↵
↵
if (r0[left] + l0[right] >= num&&r0[left]!=0) {↵
int need = num - r0[left];↵
pair<int, int> p1;↵
p1.first = (l + r) / 2 - r0[left] + 1;↵
p1.second = (l + r) / 2 + need;↵
↵
return p1;↵
}↵
if (ans[right]>=num) {↵
return getint(num, a * 2 + 1, (l + r) / 2 + 1, r);↵
}↵
assert(0);↵
}↵
int main() {↵
ifstream fin("seating.in");↵
ofstream fout("seating.out");↵
fin >> n >> m;↵
l0, r0, lazy0, lazy1, ans;↵
A.resize(n);↵
l0.resize(4 * n); r0.resize(4 * n); lazy0.resize(4 * n); lazy1.resize(4 * n); ans.resize(4 * n);↵
build(1, 0, n - 1);↵
int res = 0;↵
for (int i = 0; i < m; i++) {↵
↵
string stat;↵
fin >> stat;↵
if (stat[0] == 'A') {↵
int add; fin >> add;↵
if (ans[1] < add) {↵
res++;↵
continue;↵
}↵
pair<int, int> p = getint(add);↵
update1(p.first, p.second);↵
}↵
else {↵
int from, to; fin >> from >> to;↵
from--; to--;↵
update0(from, to);↵
}↵
}↵
fout << res << endl;↵
return 0;↵
}↵
~~~~~↵
In my segment tree, `update0` updates a given range of values to 0,` update1` updates a given range of values to 1, `updateint` updates the interval whenever some of its values have changed.`getInt(add)` gets the lowest position to insert the group of people. `lazy0` and` lazy1` stores respectively the lazy propagation for setting to 0 and setting to 1. Thank you so much for your help.↵
