oj.uz

Submission #730352

# Submission time Handle Problem Language Result Execution time Memory
730352 2023-04-25T17:51:17 Z DJeniUp Restore Array (RMI19_restore) C++17
0 / 100
 515 ms 872 KB 
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef pair<ll,ull>pairull;
typedef pair<ll,pairll>pair3l;
typedef long double ld;

#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define N 100007
#define MOD 1000000007
#define INF 100000000000007
#define eps 0.00000000001
//#define A ll(1e12)

ll n,m,r[5007],f[N];

struct D{
    ll tp,l,r,k,h;
}d[N];

int main(){

    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>d[i].l>>d[i].r>>d[i].k>>d[i].tp;
        d[i].l++;
        d[i].r++;
    }
    ll x=1;

    for(int i=1;i<=n;i++){
        ll y=0;
        for(int j=1;j<=m;j++){
            f[j]=0;
            if(d[j].l<=i && i<=d[j].r && d[j].tp==1 && d[j].h<=d[j].r-d[j].l+1-d[j].k+1)f[j]=1;
            if(d[j].l<=i && i<=d[j].r && d[j].tp==0 && d[j].h>=d[j].r-d[j].l+1-d[j].k){
                f[j]=2;
                y=1;
            }

        }
        for(int j=1;j<=m;j++){
            if(d[j].l<=i && i<=d[j].r){
                d[j].h++;
            }

        }
        if(y==0){
            r[i]=1;
        }
       // cout<<r[i]<<endl;
    }
    for(int i=1;i<=n;i++){
        ll y=0;
        ll fl=0;
        for(int j=1;j<=m;j++){
            if(d[j].l<=i && i<=d[j].r && d[j].tp==1 && d[j].h<d[j].r-d[j].l+1-d[j].k+1)fl=1;
        }
        if(fl==0)continue;
        for(int j=1;j<=m;j++){
            f[j]=0;
            if(d[j].l<=i && i<=d[j].r && d[j].tp==1)f[j]=1;
            if(d[j].l<=i && i<=d[j].r && d[j].tp==0 && d[j].h==d[j].r-d[j].l+1-d[j].k){
                f[j]=2;
                y=1;
            }
        }
        if(y==0){
            r[i]=1;
            for(int j=1;j<=m;j++){
                if(d[j].l<=i && i<=d[j].r){
                    d[j].h++;
                }

            }
            continue;
        }
        fl=0;
        while(x<i && fl==0){
            if(r[x]==0){
                x++;
                continue;
            }
            for(int j=1;j<=m;j++){
                if(d[j].l<=x && x<=d[j].r && (f[j] && d[j].h<=d[j].r-d[j].l+1-d[j].k+1)){
                    fl=-1;
                    break;
                }
                if((x<d[j].l || d[j].r<x) && f[j]==2){
                    fl=-1;
                    break;
                }
            }
            if(fl==0)fl=x;
            else fl=0;
            x++;
        }
        if(fl==0){
            cout<<-1<<endl;
            return 0;
        }
        r[fl]=0;
        r[i]=1;
        for(int j=1;j<=m;j++){
            if(d[j].l<=i && i<=d[j].r){
                d[j].h++;
            }
            if(d[j].l<=fl && fl<=d[j].r){
                d[j].h--;
            }

        }
    }
    for(int j=1;j<=m;j++){
        if(d[j].tp==0 && d[j].h>d[j].r-d[j].l+1-d[j].k){
            cout<<-1<<endl;
            return 0;
        }
        if(d[j].tp==1 && d[j].h<=d[j].r-d[j].l+1-d[j].k){
            cout<<-1<<endl;
            return 0;
        }
    }
    for(int i=1;i<=n;i++){
        cout<<r[i]<<" ";
    }
    cout<<endl;

    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 515 ms 872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 515 ms 872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -