제출 #1041293

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1041293		VMaksimoski008	Restore Array (RMI19_restore)	C++17	100 / 100	100 ms	856 KiB

restore

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    array<int, 3> E[m+2*n];
    for(int i=0; i<m; i++) {
        int l, r, k, val;
        cin >> l >> r >> k >> val; l++; r++;
        if(!val) E[i] = { l - 1, r, r - l + 1 - k };
        else E[i] = { r, l - 1, -(r - l + 1) + k - 1 };
    }

    for(int i=1; i<=n; i++) E[m+i-1] = { i-1, i, 1 };
    for(int i=1; i<=n; i++) E[m+n+i-1] = { i, i-1, 0 };

    vector<int> D(n+1, 1e9); D[0] = 0;
    for(int i=1; i<=n; i++)
        for(auto &[u, v, w] : E) D[v] = min(D[v], D[u] + w);

    for(auto &[u, v, w] : E) {
        if(D[v] > D[u] + w) {
            cout << -1 << '\n';
            return 0;
        }
    }

    for(int i=1; i<=n; i++) cout << (D[i] > D[i-1]) << " ";
    return 0;
}

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