Educational Codeforces Round 3 F. Frogs and mosquitoes

問題ページ
flogに対応する区間を持つ集合・まだ食べられていないmosquitoを保持する集合をそれぞれ保持しておく。

mosquito が現れたとする。このとき を含む区間が存在するか？存在するなら左端が最も小さいものはどれか？を判定したい。内包される区間に対応するflogが新たにmosquitoを食べることはない。内包される区間は削除しておくことにすると、 を含みうる区間は一通りに定まり、二分探索で求められる。

を含む区間の右端を 伸ばす。flogの集合のうち、内包されるようになった区間を削除しておく。削除される回数は高々1回なので計算量は問題ない。まだ食べられていないmosquitoのうち、左にいる方から順に、伸びた区間に含まれるか？を判定して伸ばす処理を行う。

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
int main(void) {  
    ll n, m;  
    cin >> n >> m;  
    vector<ll> x(n), t(n), p(m), b(m);  
    REP(i, n) cin >> x[i] >> t[i];  
    REP(i, m) cin >> p[i] >> b[i];  
  
    set<PII> flog;  
    {  
        vector<ll> ord(n);  
        iota(ALL(ord), 0);  
        sort(ALL(ord), [&](ll l, ll r){  
            return PII(x[l], x[l]+t[l]) < PII(x[r], x[r]+t[r]);  
        });  
        for(auto i: ord) {  
            // 内包されるならスルー  
            if(flog.size() && x[i]+t[i] <= flog.rbegin()->first) continue;  
            flog.insert({x[i]+t[i], i});  
        }  
    }  
  
    vector<ll> cnt(n);  
    // 区間idxをlen長くする  
    auto extend = [&](ll idx, ll len) {  
        flog.erase({x[idx]+t[idx], idx});  
        while(1) {  
            // r <= x[idx]+t[idx]+len の区間を消す  
            auto itr = flog.lower_bound({x[idx]+t[idx], 0});  
            if(itr != flog.end() && itr->first <= x[idx]+t[idx]+len) flog.erase(itr);  
            else break;  
        }  
        cnt[idx]++;  
        t[idx] += len;  
        flog.insert({x[idx]+t[idx], idx});  
    };  
  
    multiset<PII> rest;  
    REP(i, m) {  
        auto itr = flog.lower_bound({p[i], 0});  
        if(itr != flog.end() && x[itr->second] <= p[i]) {  
            ll idx = itr->second;  
            extend(idx, b[i]);  
  
            while(1) {  
                auto ritr = rest.lower_bound({x[idx], 0});  
                if(ritr!=rest.end() && ritr->first <= x[idx]+t[idx]) {  
                    extend(idx, ritr->second);  
                    rest.erase(ritr);  
                } else {  
                    break;  
                }  
            }  
        } else {  
            rest.insert({p[i], b[i]});  
        }  
    }  
  
    REP(i, n) cout << cnt[i] << " " << t[i] << "\n";  
  
    return 0;  
}  

setとmultisetを間違えて1時間半溶かしました