I've this test wrong too. Here's my code:
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
#include <ctime>
using namespace std;
#define forn(i,n) for (int i = 0; i < (int)n; i++)
struct bus {
int l, r, type, num;
friend bool operator<(const bus &bus1, const bus &bus2) {
if (bus1.type != bus2.type) {
return bus1.r < bus2.r;
} else {
return bus1.num < bus2.num;
}
}
};
int n, m;
vector<pair<int, int> > v1, v2;
bus mas[300000];
multiset<bus> s;
multiset<bus>::iterator iter;
int main() {
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
scanf("%d", &n);
v1.resize(n);
forn(i,n) {
scanf("%d%d", &v1[i].first, &v1[i].second);
v1[i].second += v1[i].first - 1;
}
scanf("%d", &m);
v2.resize(m);
forn(i,m) {
scanf("%d%d", &v2[i].first, &v2[i].second);
v2[i].second += v2[i].first - 1;
}
for (int i = 1; i <= n; i++) {
mas[i].l = v1[i - 1].first;
mas[i].r = v1[i - 1].second;
mas[i].type = 1;
mas[i].num = i;
}
for (int i = 1; i <= m; i++) {
mas[i + n].l = v2[i - 1].first;
mas[i + n].r = v2[i - 1].second;
mas[i + n].type = 2;
mas[i + n].num = i;
}
int p1 = 1, p2 = n + 1;
int t = min(mas[p1].l, mas[p2].l);
while ((p1 <= n && p2 <= m + n) || t <= 230000000) {
while (p1 <= n && mas[p1].l <= t) {
if (mas[p1].r < t) {
printf("NO");
return 0;
} else {
s.insert(mas[p1++]);
}
}
while (p2 <= m + n && mas[p2].l <= t) {
if (mas[p2].r < t) {
printf("NO");
return 0;
} else {
s.insert(mas[p2++]);
}
}
iter = s.begin();
if (iter != s.end()) {
if ((*iter).r < t) {
printf("NO");
return 0;
} else {
s.erase(iter);
}
t++;
} else {
t = 230000000;
if (p1 <= n) {
t = min(t, mas[p1].l);
}
if (p2 <= n + m) {
t = min(t, mas[p2].l);
}
if (t == 230000000) {
printf("YES");
return 0;
}
}
}
printf("YES");
//printf("%.5lf", 1.0 * clock() / (1.0 * CLOCKS_PER_SEC));
}
Where's bug?
