Submission #923814

#	Time	Username	Problem	Language	Result	Execution time	Memory
923814		aykhn	Restore Array (RMI19_restore)	C++17	20 / 100	360 ms	1040 KiB

restore

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

const short MXN = 5e3 + 5;

short n, m;
vector<array<short, 3>> ed;
short dist[MXN];

short add(short a, short b)
{
    return a + b;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> m;
    for (short i = 0; i < n; i++)
    {
        ed.push_back({i, add(i, 1), 1});
        ed.push_back({add(i, 1), i, 0});
    }
    for (short i = 1; i <= n; i++) dist[i] = add(n, 10);
    while (m--)
    {
        short l, r, k, v;
        cin >> l >> r >> k >> v;
        r++;
        short sz = r - l;
        if (v == 1)
        {
            short mx = sz;
            short mn = sz - k + 1;
            ed.push_back({l, r, mx});
            ed.push_back({r, l, (short)(-mn)});
        }
        else
        {
            short mn = 0;
            short mx = sz - k;
            ed.push_back({l, r, mx});
            ed.push_back({r, l, (short)(-mn)});
        }
    }
    bool f = 0;
    for (short i = 1; i <= n + 1; i++)
    {
        f = 0;
        for (const array<short, 3> &x : ed)
        {
            if (add(dist[x[0]], x[2]) < dist[x[1]]) 
            {
                f = 1;
                dist[x[1]] = add(dist[x[0]], x[2]);
            }
        }
    }
    if (f)
    {
        cout << -1 << '\n';
        return 0;
    }
    for (short i = 1; i <= n; i++)
    {
        cout << dist[i] - dist[i - 1] << ' ';
    }
    cout << '\n';
}

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