Submission #961564

#	Time	Username	Problem	Language	Result	Execution time	Memory
961564		blacktulip	Restore Array (RMI19_restore)	C++17	0 / 100	104 ms	1112 KiB

restore

#include<bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define pb push_back
#define fi first
#define se second
 
const int li=500005;
int x[li],y[li],w[li],c[li],n,m;
vector<pair<int,pair<int,int>>> v;
 
void bellman_ford(){
	for(int j=1;j<=n+1;j++){
		for(auto go:v){
			if(c[go.fi]+go.se.se<c[go.se.fi]){
				if(j==n+1){cout<<"-1\n";exit(0);}
				c[go.se.fi]=c[go.fi]+go.se.se;
			}
		}
	}
}
 
int32_t main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){
		v.pb({i,{i+1,1}});
		v.pb({i+1,{i,0}});
	}
	for(int i=1;i<=m;i++){
		int l,r,k,value;
		cin>>l>>r>>k>>value;
		if(value==0){
			v.pb({l,{r+1,r-l+1-k}});
		}
		else v.pb({r+1,{l,r-l+1-k+1}});
	}
	c[0]=0;
	for(int i=1;i<=n;i++)c[i]=100000000000000;
	bellman_ford();
	for(int i=1;i<=n;i++){
		cout<<c[i]-c[i-1]<<" ";
	}
}

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