Submission #857540

#	Time	Username	Problem	Language	Result	Execution time	Memory
857540		lbadea1000	Restore Array (RMI19_restore)	C++17	13 / 100	434 ms	864 KiB

restore

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

const int NMAX = 5e3;
const int MMAX = 1e4;

int ans[NMAX];

struct op {
    int l, r, minimum, nr;
    bool active;
} v[MMAX];


int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int l, r, k, nr;
        cin >> l >> r >> k >> nr;
        if(nr == 0) {
            v[i] = {l, r, k, 0, true};
        } else {
            v[i] = {l, r, r - l + 1 - k + 1, 1, true};
        }
    }
    bool isPossible = true;
    for(int i = 0; i < n; i++) {
        int max0 = 0, max1 = 0;
        for(int j = 0; j < m; j++) {
            if(v[j].active) {
                if(v[j].l == i) {
                    if(v[j].nr == 0)
                        max0 = max(max0, v[j].minimum);
                    else max1 = max(max1, v[j].minimum);
                }
            }
        }
        if(max0 > max1) {
            ans[i] = 0;
        } else ans[i] = 1;
        for(int j = 0; j < m; j++) {
            if(v[j].active) {
                if(v[j].l == i) {
                    if(v[j].nr == ans[i])
                        v[j].minimum--;
                    v[j].l++;
                    if(v[j].l > v[j].r) {
                        if(v[j].minimum > 0)
                            isPossible = false;
                        else
                            v[j].active = false;
                    }
                }
            }
        }
    }
    if(isPossible) {
        for(int i = 0; i < n; i++)
            cout << ans[i] << ' ';
    } else cout << -1;
    return 0;
}

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