Submission #1245171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245171		Thunnus	Restore Array (RMI19_restore)	C++20	100 / 100	279 ms	1136 KiB

restore

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

const int INF = 1e18;

inline void solve(){
    int n, m;
    cin >> n >> m;
    vector<array<int, 3>> edges(m);
    for(int i = 0; i < m; i++){
        int l, r, k, val;
        cin >> l >> r >> k >> val;
        l++, r++;
        if(val){
            edges[i] = {r, l - 1, (k - 1) - (r - l + 1)};
        }
        else{
            edges[i] = {l - 1, r, (r - l + 1) - k};
        }
    }
    for(int i = 1; i <= n; i++){
        edges.emplace_back(array<int, 3>{i, i - 1, 0});
        edges.emplace_back(array<int, 3>{i - 1, i, 1});
    }

    vi dist(n + 1, INF);
    auto bellman_ford = [&]() -> bool {
        dist[0] = 0;
        int lst = -1;
        for(int i = 0; i < n; i++){
            lst = -1;
            for(array<int, 3> &edge : edges){
                int a = edge[0], b = edge[1], w = edge[2];
                if(dist[a] < INF && dist[b] > dist[a] + w){
                    dist[b] = max(-INF, dist[a] + w);
                    lst = b;
                }
            }
        }
        return (lst == -1);
    };
    
    if(bellman_ford()){
        for(int i = 1; i <= n; i++){
            cout << dist[i] - dist[i - 1] << " ";
        }
        cout << "\n";
    }
    else{
        cout << "-1\n";
    }
    return;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

/*
(l, r, k, 1) -> number of 0 < k, number of 1 > len - k -> pref[r] - pref[l - 1] >= (r - l + 1) - (k - 1) -> pref[r] + k - r + l >= pref[l - 1] 
(l, r, k, 0) -> number of 0 >= k, number of 1 <= len - k -> pref[r] - pref[l - 1] <= (r - l + 1) - k -> pref[l - 1] + (r - l + 1) - k >= pref[r]
pref[i] + 0 >= pref[i - 1]
pref[i - 1] + 1 >= pref[i];
*/

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