Submission #659498

#	Time	Username	Problem	Language	Result	Execution time	Memory
659498		AlesL0	Restore Array (RMI19_restore)	C++17	13 / 100	233 ms	1228 KiB

restore

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = 1000000000;

struct query {
    ll l, kk, bigger;
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, m; cin >> n >> m;
    vector <query> q[n+1];
    vector <ll> dpmin(n+1, -INF), dpmax(n+1, INF);
    dpmin[0] = 0;
    dpmax[0] = 0;
    while (m--){
        ll l, r, k, value; cin >> l >> r >> k >> value;
        r++; l++;
        if (value){
            q[r].push_back({l-1, r-l+2-k, 1});
        }
        else q[r].push_back({l-1, r-l+1-k, 0});
    }
    for (int i = 1; i <= n; i++){
        q[i].push_back({i-1, 0, 1});
        q[i].push_back({i-1, 1, 0});
    }
    for (int i = 1; i <= n; i++){
        for (auto x : q[i]){
            if (x.bigger)dpmin[i] = max(dpmin[i], dpmin[x.l]+x.kk);
            else dpmax[i] = min(dpmax[i], dpmax[x.l]+x.kk);
        }
        for (int j = i; j >= 1; j--){
            for (auto x : q[j]){
                if (x.bigger)dpmax[x.l] = min(dpmax[x.l], dpmax[j]-x.kk);
                else dpmin[x.l] = max(dpmin[x.l], dpmin[j]-x.kk);
            }
        }
    }
    //for (int i = 0; i <= n; i++)cerr << dpmin[i] << " " << dpmax[i] << "\n";
    for (int i = 0; i <= n; i++){
        if (dpmin[i] > dpmax[i]){
            cout << -1;
            return 0;
        }
    }
    for (int i = 0; i < n; i++)cout << dpmin[i+1]-dpmin[i] << " ";
}

• Subtask 1: 0 / 7
• Subtask 2: 13 / 13
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55