メモ

自分に向けて書いたメモを取り扱っています.

AOJ 0231 Dangerous Bridge

解法

高々100人の情報しかないので、座標圧縮すると最大でも200回ループ回せば終わる。

ソースコード

struct P {
    int m;
    long long a, b;
};

int n, from[128], to[128], sum[128];
P p[128];

int main() {
    while(scanf("%d", &n) && n) {
        string ans = "OK";
        memset(sum, 0, sizeof sum);
        vector<long long> x;

        for(int i = 0; i < n; i++) {
            scanf("%d%lld%lld", &(p[i].m), &(p[i].a), &(p[i].b));
            x.push_back(p[i].a); x.push_back(p[i].b);
        }

        sort(x.begin(), x.end());
        x.erase(unique(x.begin(), x.end()), x.end());

        for(int i = 0; i < n; i++) {
            from[i] = lower_bound(x.begin(), x.end(), p[i].a) - x.begin();
            to[i] = lower_bound(x.begin(), x.end(), p[i].b) - x.begin();
        }

        for(int i = 0; i < n; i++) {
            for(int j = from[i]; j < to[i]; j++) {
                sum[j] += p[i].m;
            }
        }

        for(int i = 0; i < x.size(); i++) {
            if(sum[i] > 150) {
                ans = "NG";
                break;
            }
        }

        cout << ans << endl;
    }
}

やっと300問…。部活に忙しい毎日…