Problem Description
…,A−3,A−2,A−1,A0,A1,A2,A3,…. Each processing units has a pointer to mark exactly one grid in the memory. In each clock turn, the pointer would stay at the current grid, move the pointer one grid forward, or move the pointer one grid backward. In their work, Alice and Bob would submit their codes, and their programs would start at the same time. Initially, both pointers would be located at a random grid, and move according to a set of instructions. If both pointers are at the same grid at the same time, the confliction counter would plus one and record it(If their initial grids are the same, the counter would still record it). Now it is your job to find the maximum conflictions the counter could record.
Input
The first line is the number of test cases.
For each test case, the first is an integer
NAlice(NAlice≤100000), donating the length of the instructions of Alice.
The next
NAlice lines describe Alice`s instructions. Each line consists of two integer
c,t.
c could be
−1,0,1, donating moving forward, staying, and moving backward respectively.
t is a non-negative integer donating that the instruction
c would be executed
t times, in the next
t clock turns.
The next line is an integer
NBob(NBob≤100000), donating the length of the instructions of Bob.
The next
NBob lines describe Bob`s instructions. Each line consists of two integer
c,t.
c could be
−1,0,1, donating moving forward, staying, and moving backward respectively.
t is a non-negative integer donating that the instruction
c would be executed
t times, in the next
t clock turns.
Suppose
LAlice equals the sum of all
t in Alice's program, and
LBob equals the sum of all
t in Bob's program.
It is guaranteed
LAlice=LBob and
LAlice,LBob≤1018.
Output
For each test case, output a line containing the maximum conflictions.
Sample Input
2
1
1 2
2
1 1
-1 1
1
0 6
4
-1 2
1 1
-1 2
1 1
Sample Output
2
3
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 6e5 + 10;
int T, n, m, sz;
long long ca[N], ta[N], cb[N], tb[N];
struct point {
long long r, add;
long long odd, even;
point() {}
point(long long r, long long odd, long long even, long long add) :r(r), odd(odd), even(even), add(add) {}
bool operator<(const point a) {
return r == a.r ? add > a.add : r < a.r;
}
}g[N];
int main() {
for (scanf("%d", &T); T--;) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld%lld", &ca[i], &ta[i]);
}
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
scanf("%lld%lld", &cb[i], &tb[i]);
}
sz = 0;
g[sz++] = point(0, 1, 1, 1);
g[sz++] = point(1, 1, 1, -1);
for (long long c = 0, i = 1, j = 1; i <= n && j <= m;) {
long long tc = min(ta[i], tb[j]);
long long l = c, r = c;
if (ca[i] == cb[j]) {
int flag = l % 2 ? 1 : 0;
g[sz++] = point(l, flag, !flag, tc);
g[sz++] = point(r + 1, flag, !flag, -tc);
}
else {
if (ca[i] == 0) {
if (cb[j] == 1) l -= tc, c -= tc, r--;
else r += tc, c += tc, l++;
int flag = l % 2 ? 1 : 0;
g[sz++] = point(l, flag, !flag, 1);
g[sz++] = point(l + 1, !flag, flag, 1);
g[sz++] = point(r + 1, 1, 1, -1);
}
else if (cb[j] == 0) {
if (ca[i] == 1) r += tc, c += tc, l++;
else l -= tc, c -= tc, r--;
int flag = l % 2 ? 1 : 0;
g[sz++] = point(l, flag, !flag, 1);
g[sz++] = point(l + 1, !flag, flag, 1);
g[sz++] = point(r + 1, 1, 1, -1);
}
else {
if (ca[i] == 1) r += tc + tc, c += tc + tc, l += 2;
else l -= tc + tc, c -= tc + tc, r -= 2;
int flag = l % 2 ? 1 : 0;
g[sz++] = point(l, flag, !flag, 1);
g[sz++] = point(r + 1, flag, !flag, -1);//.
}
}
if (!(ta[i] -= tc)) i++;
if (!(tb[j] -= tc)) j++;
}
sort(g, g + sz);
long long odd = 0, even = 0, ans = 0;
for (int i = 0, j = 0; i < sz; i = j) {
for (j = i; j < sz && g[i].r == g[j].r; j++) {
odd += g[j].odd * g[j].add;
even += g[j].even * g[j].add;
}
ans = max(ans, max(odd, even));
}
printf("%lld\n", ans);
}
return 0;
}