Submission #1200027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200027		abdelaal_03	Restore Array (RMI19_restore)	C++20	100 / 100	294 ms	852 KiB

restore

#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
typedef long long ll;
typedef long double ld;
typedef long long ll;
const long double PI = 3.141592654;
const long long md = 1e9 + 7;
#define xi first
#define yi second
#define MAX int(3e5)+7
#define INF (ll)1e9
#define SQ 500

long long gcd(long long a, long long b) {
    if (b == 0)return a;
    return (a % b) ? gcd(b, a % b) : b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin>>n>>m;
    vector<pair<int, pair<int, int>>>edg(m);
    for (int i = 0; i < m; i++) {
        int l, r, k, val;
        cin>>l>>r>>k>>val;
        l++, r++;
        if (val == 0) {
            edg[i] = {r - l + 1 - k,{l - 1, r}};
        }else {
            edg[i] = {(r - l + 1 - k + 1) * -1,{r, l - 1}};
        }
    }
    for (int i = 1; i <= n; i++) {
        edg.push_back({1,{i - 1, i}});
        edg.push_back({0,{i, i - 1}});
    }
    for (int i = 0; i <= n; i++) {
        edg.push_back({0,{n + 1, i}});
    }
    vector<ll> d(n + 2, INF);
    d[n + 1] =  d[0] =  0;
    int x;
    for (int i = 0; i < n + 2; i++) {
        x = -1;
        for (auto &e : edg) {
            if (d[e.yi.xi] < INF) {
                if (d[e.yi.yi] > d[e.yi.xi] + e.xi) {
                    d[e.yi.yi] = max(-INF, d[e.yi.xi] + e.xi);
                    x = e.yi.yi;
                }
            }
        }
    }
    if (x == -1) {
        for (int i = 1; i <= n; i++) {
            if (d[i] > d[i - 1]) cout<<1<<" ";
            else cout<<0<<" ";
        }
        cout<<endl;
    }else cout<<-1<<endl;

    return 0;
}

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