Submission #1185070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185070		12345678	Restore Array (RMI19_restore)	C++20	38 / 100	79 ms	107076 KiB

restore

#include <bits/stdc++.h>

using namespace std;

const int nx=5e3+5;

int n, m, f0[nx], f1[nx], l, r, k, v, mx0[nx], mx1[nx], dp0[nx][nx], dp1[nx][nx], can0[nx], vl0[nx], can1[nx], vl1[nx], res[nx];
pair<int, pair<int, int>> cur;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    dp0[0][0]=dp1[0][0]=1;
    for (int i=1; i<=m; i++)
    {
        cin>>l>>r>>k>>v;
        l++, r++;
        if (k==1)
        {
            if (v==0) mx1[r]=max(mx1[r], l);
            else for (int j=l; j<=r; j++) f1[j]=1;
        }
        else
        {
            if (v==1) mx0[r]=max(mx0[r] ,l);
            else for (int j=l; j<=r; j++) f0[j]=1; 
        }
    }
    /*
    cout<<"fix one : ";
    for (int i=1; i<=n; i++) cout<<f1[i]<<' ';
    cout<<'\n';
    cout<<"fix zero : ";
    for (int i=1; i<=n; i++) cout<<f0[i]<<' ';
    cout<<'\n';
    */
    can0[0]=can1[0]=1;
    for (int i=1; i<=n; i++)
    {
        for (int j=0; j<i; j++)
        {
            if (!f1[i]&&mx0[i]<=j)
            {
                if (j==i-1) dp0[i][j]=can1[j];
                else dp0[i][j]=dp0[i-1][j];
            }
            if (!f0[i]&&mx1[i]<=j)
            {
                if (j==i-1) dp1[i][j]=can0[j];
                else dp1[i][j]=dp1[i-1][j];
            }
            if (dp0[i][j]&&!can0[i]) vl0[i]=j;
            can0[i]|=dp0[i][j];
            if (dp1[i][j]&&!can1[i]) vl1[i]=j;
            can1[i]|=dp1[i][j];
            //cout<<"dp "<<i<<' '<<j<<' '<<dp0[i][j]<<' '<<dp1[i][j]<<'\n';
        }
    }
    if (!can0[n]&&!can1[n]) return cout<<-1, 0;
    if (can0[n]) cur={0, {n, vl0[n]}};
    else cur={1, {n, vl1[n]}};
    while (cur.second.first!=0)
    {
        auto [i, j]=cur.second;
        auto s=cur.first;
        res[i]=s;
        if (s==0)
        {
            if (j==i-1) cur={1, {i-1, vl1[i-1]}};
            else cur={0, {i-1, j}};
        }
        else
        {
            if (j==i-1) cur={0, {i-1, vl0[i-1]}};
            else cur={1, {i-1, j}};
        }
    }
    for (int i=1; i<=n; i++) cout<<res[i]<<' ';
}

/*
4 5
0 1 2 1
0 2 1 0
2 2 1 0
0 1 1 0
1 2 1 0

*/

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