oj.uz

Submission #923814

# Submission time Handle Problem Language Result Execution time Memory
923814 2024-02-07T19:53:11 Z aykhn Restore Array (RMI19_restore) C++17
20 / 100
 360 ms 1040 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 752 KB Output is correct
2 Correct 134 ms 756 KB Output is correct
3 Correct 133 ms 604 KB Output is correct
4 Correct 136 ms 752 KB Output is correct
5 Correct 354 ms 600 KB Output is correct
6 Correct 360 ms 856 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 752 KB Output is correct
2 Correct 134 ms 756 KB Output is correct
3 Correct 133 ms 604 KB Output is correct
4 Correct 136 ms 752 KB Output is correct
5 Correct 354 ms 600 KB Output is correct
6 Correct 360 ms 856 KB Output is correct
7 Correct 142 ms 900 KB Output is correct
8 Correct 149 ms 860 KB Output is correct
9 Correct 149 ms 904 KB Output is correct
10 Correct 144 ms 1040 KB Output is correct
11 Incorrect 134 ms 896 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 141 ms 752 KB Output is correct
12 Correct 134 ms 756 KB Output is correct
13 Correct 133 ms 604 KB Output is correct
14 Correct 136 ms 752 KB Output is correct
15 Correct 354 ms 600 KB Output is correct
16 Correct 360 ms 856 KB Output is correct
17 Correct 142 ms 900 KB Output is correct
18 Correct 149 ms 860 KB Output is correct
19 Correct 149 ms 904 KB Output is correct
20 Correct 144 ms 1040 KB Output is correct
21 Incorrect 134 ms 896 KB Output isn't correct
22 Halted 0 ms 0 KB -