제출 #997261

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
997261		amirhoseinfar1385	Restore Array (RMI19_restore)	C++17	100 / 100	235 ms	1112 KiB

restore

#include<bits/stdc++.h>
using namespace std;
const int maxn=5000+10;
vector<pair<int,int>>adj[maxn];
int f=0,n,m,dis[maxn];
/*
	if w==0{
		ps[r]<=ps[l]+(len-k)
	}else{
		ps[r]-(len-k+1)>=ps[l]
	}
*/

void vorod(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		adj[i-1].push_back(make_pair(1,i));
		adj[i].push_back(make_pair(0,i-1));
	}
	for(int i=0;i<m;i++){
		int l,r,k,w;
		cin>>l>>r>>k>>w;
		r++;
		int len=r-l;
		if(w==0){
			adj[l].push_back(make_pair(len-k,r));
		}else{
			adj[r].push_back(make_pair(-(len-k+1),l));
		}
	}
}

void caldis(){
	dis[0]=0;
	for(int i=1;i<=n;i++){
		dis[i]=n*10;
	}
	for(int ted=0;ted<=n;ted++){
		for(int i=0;i<=n;i++){
			for(auto x:adj[i]){
				dis[x.second]=min(dis[x.second],dis[i]+x.first);
			}
		}
	}
	for(int i=0;i<=n;i++){
		for(auto x:adj[i]){
			if(dis[x.second]>dis[i]+x.first){
				f=1;
				break;
			}
		}
	}
}

void khor(){
	if(f){
		cout<<-1<<"\n";
		return ;
	}
	for(int i=1;i<=n;i++){
		if(dis[i]==dis[i-1]){
			cout<<0<<" ";
		}else{
			cout<<1<<" ";
		}
	}
	cout<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	vorod();
	caldis();
	khor();
}

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