D - Choose Your Characters

D - Choose Your Characters

都合のため、iはiに対して不利とする

解法

rok[l] := lに対して、選べる最小のr

上が出来れば解ける

例えばi に対して不利なキャラが 2 3 5 6 7の時、

rok[7] = max(rok[7],8 )

rok[6] = max(rok[6],8 ) 

rok[5] = max(rok[5],8 )

rok[3] = max(rok[3],4 )

rok[2] = max(rok[2],4 )

となる 

これはiに対して不利なキャラを大きい順に走査すればできる

上をすべてのiについてやる

Sign In - AtCoder

void solve() {
    cin >> n >> m;
    _vvi to(n);
    rep(i, m) {
        int f = in() - 1, t = in() - 1;
        to[f] += t;
    }
    vi rok;
    iota(rok, 0, n);
    rep(i, n) {
        to[i] += i;
        sort(to[i]);
        to[i] += -1;
        int r = 0;
        rer(j, sz(to[i]) - 2) {
            int l = to[i][j];
            int nl = to[i][j + 1];
            if (l + 1 != nl) {
                r = l + 1;
            }
            chmax(rok[l], r);
        }
    }
    int res = inf;
    int l = 0, r = 0;
    rep(i, n) {
        if (rok[i] == n )con;
        if (chmin(res, rok[i] - i)) {
            l = i + 1, r = rok[i] + 1;
        }
    }
    if (res == inf)cout << -1 << endl;
    else cout << l << " " << r << endl;
}