Submission #1201986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201986		negart	Restore Array (RMI19_restore)	C++20	13 / 100	109 ms	804 KiB

restore

// ~ be name khoda ~ //

#include<bits/stdc++.h>

using namespace std;

const int MAX_N = 5e3 + 10;
const int MAX_M = 2e4 + 10;

vector <tuple<int, int, int>> e;
int n, m, dis[MAX_N], ans[MAX_N];

bool check() {
    for(int i = 0; i < e.size(); i++) {
        auto [v, u, w] = e[i];
        if(dis[u] > dis[v] + w)
            return true;
    }
    return false;
}

int main() {
    cin >> n >> m;
    memset(dis, 63, sizeof dis);
    for(int i = 0; i < m; i++) {
        int l, r, k, val;
        cin >> l >> r >> k >> val;
        l++;
        r++;
        if(val == 0) {
            e.push_back({l - 1, r, r - l + 1 - k});
        }
        else {
            e.push_back({r, l - 1, -r + l - 2 + k});
        }
    }
    
    for(int i = 1; i < n; i++) {
        e.push_back({i, i + 1, 1});
        e.push_back({i + 1, i, 1});
    }

    dis[0] = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < e.size(); j++) {
            auto [v, u, w] = e[j];
            dis[u] = min(dis[u], dis[v] + w);
        }
    }
    if(check()) {
        cout << -1 << endl;
        return 0;
    }
    else {
        for(int i = 1; i <= n; i++) {
            if(dis[i] == dis[i - 1])
                cout << 0 << " ";
            else if(dis[i] > dis[i - 1])
                cout << 1 << " ";
            else
                cout << 0 << " ";
        }
    }
}

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