mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #210 (Div. 1) A. Levko and Array Recovery

解法

配列 a の j 番目の数が i 番目のクエリの時点で +k されているとしましょう。この時, j を含む区間 [l, r] において最大値が d になっているというヒントが与えられたとすると, j 番目の数は d-k 以下になっていなければなりません。

このような感じで, a[j] の値が制限されます。この値を xj としましょう。a[j] の値は xj 以下なら何でも良いですが, 指定された値未満にしても特に良いことがないので, xj で決定します。
あとは, 与えられたクエリを満たす数列が存在するかを判定すればよいですが, これは数列についてシミュレーションして試せば良いです。

const int MAXN = 5055;
const int INF = 5e8;
int a[MAXN];
int t[MAXN], l[MAXN], r[MAXN], d[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) a[i] = INF;
    for (int i = 0; i < m; i++) {
        cin >> t[i] >> l[i] >> r[i] >> d[i];
        l[i]--; r[i]--;
    }
    for (int i = 0; i < n; i++) {
        int plus = 0;
        for (int j = 0; j < m; j++) {
            if (t[j] == 1 && l[j] <= i && i <= r[j]) {
                plus += d[j];
            }
            if (t[j] == 2 && l[j] <= i && i <= r[j]) {
                a[i] = min(a[i], d[j]-plus);
            }
        }
    }
    vector<int> ans(n);
    for (int i = 0; i < n; i++) ans[i] = a[i];
    for (int i = 0; i < m; i++) {
        if (t[i] == 1) {
            for (int j = l[i]; j <= r[i]; j++) a[j] += d[i];
        } else {
            int maxi = -INF;
            for (int j = l[i]; j <= r[i]; j++) maxi = max(maxi, a[j]);
            if (maxi != d[i]) {
                cout << "NO" << endl;
                return 0;
            }
        }
    }
    cout << "YES" << endl;
    for (int el : ans) cout << el << " ";
    cout << endl;
    return 0;
}