Submission #484846

#	Time	Username	Problem	Language	Result	Execution time	Memory
484846		blue	Restore Array (RMI19_restore)	C++17	100 / 100	355 ms	972 KiB

restore

#include <iostream>
#include <vector>
using namespace std;

using vi = vector<int>;
#define pb push_back

const int INF = 1'000'000;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    cin >> N >> M;

    vi u, v, w;

    for(int j = 1; j <= M; j++)
    {
        int l, r, k, val;
        cin >> l >> r >> k >> val;
        l++;
        r++;

        if(val == 0)
        {
            u.pb(l-1);
            v.pb(r);
            w.pb(r-l+1 - k);
        }
        else
        {
            u.pb(r);
            v.pb(l-1);
            w.pb(-(r-l+2 - k));
        }
    }

    for(int i = 0; i < N; i++)
    {
        u.pb(i);
        v.pb(i+1);
        w.pb(1);

        u.pb(i+1);
        v.pb(i);
        w.pb(0);
    }

    vi sp(1+N, INF);
    sp[0] = 0;

    for(int q = 1; q <= N; q++)
    {
        for(int j = 0; j < 2*N+M; j++)
        {
            sp[v[j]] = min(sp[v[j]], sp[u[j]] + w[j]);
        }
    }

    bool works = 1;
    for(int j = 0; j < 2*N+M; j++)
        if(sp[v[j]] > sp[u[j]] + w[j])
            works = 0;

    // cerr << u[0] << ' '<< v[0] << ' ' << w[0] << '\n';

    if(!works) cout << "-1\n";
    else
    {
        for(int i = 1; i <= N; i++)
        {
            cout << (sp[i] != sp[i-1]) << ' ';
        }
        cout << '\n';
    }
}

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