Submission #1185284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185284		12345678	Restore Array (RMI19_restore)	C++20	100 / 100	239 ms	832 KiB

restore

#include <bits/stdc++.h>

using namespace std;

const int nx=5e3+5;

int n, m, l, r, v, k, mn[nx];
vector<tuple<int, int, int>> edg;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n; i++) mn[i]=n+1, edg.push_back({i, i-1, 0}), edg.push_back({i-1, i, 1});
    for (int i=1; i<=m; i++)
    {
        cin>>l>>r>>k>>v;
        r++;
        if (v==1) edg.push_back({r, l, -(r-l-k+1)}); // x[r]>=x[l]+(r-l-k+1)
        else edg.push_back({l, r, r-l-k}); // x[r]<=x[l]+
    }
    for (int i=1; i<=n; i++) for (auto [u, v, w]:edg) if (mn[v]>mn[u]+w) mn[v]=mn[u]+w;
    for (auto [u, v, w]:edg) if (mn[v]>mn[u]+w) return cout<<-1, 0;
    for (int i=1; i<=n; i++) cout<<((mn[i]==mn[i-1])?0:1)<<' ';
}

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