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?

1
1 3
2
1 4
1 2

answer is "YES"

Ac!! after some correction!
Hint: passed time and waited time  need to corrected (i.e. change to real values)

Write your e-mail.
I help you.

Yes.

Greedy algorithm.
For every bus you can comptute "Critical time"=p[i]+t[i]-i.
If 1st Bus from "Small Vasyuki" will pass the road after critical time of ith bus from "Small Vasyuki" then ith bus will be late. If jth bus from "Small Vasyuki" will pass the road after (critical time + j-1) then ith bus will be late.

If k1-1 buses from "Small Vasyuki" passed and k2-1 buses from "Big Vasyuki" passed then buses from direction with lower critcaltime(of some bus)+k (k1 or k2) are prefered.


Edited by author 17.10.2010 14:17

Is the ans YES?
But I wa on 10...
Greedy...