Submission #961121

#	Time	Username	Problem	Language	Result	Execution time	Memory
961121		blacktulip	Restore Array (RMI19_restore)	C++17	100 / 100	319 ms	1304 KiB

restore

#include <bits/stdc++.h>
using namespace std;
 
const int MXN = 5e3 + 5;
 
int n, m;
vector<array<int, 3>> ed;
int dist[MXN];
 
int add(int a, int b)
{
    return a + b;
}
 
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        ed.push_back({i, add(i, 1), 1});
        ed.push_back({add(i, 1), i, 0});
    }
    for (int i = 1; i <= n; i++) dist[i] = add(n, 10);
    while (m--)
    {
        int l, r, k, v;
        cin >> l >> r >> k >> v;
        r++;
        int sz = r - l;
        if (v == 1)
        {
            int mx = sz;
            int mn = sz - k + 1;
            ed.push_back({r, l, (int)(-mn)});
        }
        else
        {
            int mn = 0;
            int mx = sz - k;
            ed.push_back({l, r, mx});
        }
    }
    bool f = 0;
    for (int i = 1; i <= n + 1; i++)
    {
        f = 0;
        for (const array<int, 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 (int i = 1; i <= n; i++)
    {
        cout << dist[i] - dist[i - 1] << ' ';
    }
    cout << '\n';
}

Compilation message (stderr)

restore.cpp: In function 'int main()':
restore.cpp:34:17: warning: unused variable 'mx' [-Wunused-variable]
   34 |             int mx = sz;
      |                 ^~
restore.cpp:40:17: warning: unused variable 'mn' [-Wunused-variable]
   40 |             int mn = 0;
      |                 ^~

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