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問…。部活に忙しい毎日…