제출 #966910

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

restore

#include <bits/stdc++.h>

// author : a1abay

using namespace             std;

int n, m, l, r, k, v;
vector<array<int, 3>> e;

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    vector<int> d(n + 1, n + 1);
    for(int i = 0; i < n; i++)
    {
        e.push_back({i, i + 1, 1});
        e.push_back({i + 1, i, 0});
    }
    while(m--)
    {
        cin >> l >> r >> k >> v;
        if(!v) e.push_back({l, r + 1, r - l + 1 - k});
        else e.push_back({r + 1, l, -(r - l + 1 - k + 1)});
    }
    d[0] = 0;
    for(int i = 1; i <= n; i++)
    {
        for(auto p : e)
        {
            if(d[p[0]] + p[2] < d[p[1]])
            {
                d[p[1]] = d[p[0]] + p[2];
                if(i == n)
                {
                    cout << -1;
                    return 0;
                }
            }
        }
    }
    for(int i = 1; i <= n; i++) cout << d[i] - d[i - 1] << ' ';
}

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